# Prime number algorithm in C

Discussion in 'C Programming' started by Cmorriskuerten, Nov 17, 2003.

1. ### CBFalconerGuest

If you are willing to settle for the root of (<T>_MAX + 1), which
must be of the form 2**n, simpler methods are available. At worst
the root of 2 may be involved, for n odd.

CBFalconer, Nov 21, 2003

2. ### Dave ThompsonGuest

Add parens ( (v) <= (n)/(v) ) to be safe in all uses.
Or (in both versions) v * v <= n, which faster on nearly all
platforms, often much faster.

Or, less general, strength-reduce vsquared in the loop by adding 2*v-1
for each increment, or 2*(v-1)+2*v-2 aka 4*v-4 for increment-by-2.

- David.Thompson1 at worldnet.att.net

Dave Thompson, Nov 22, 2003

3. ### James HuGuest

Yes, thanks.
But this is prone to overflow.

-- James

James Hu, Nov 22, 2003
4. ### Dan PopGuest

Show us the code, as a constant expression that can be evaluated at
compile time.

Dan

Dan Pop, Nov 24, 2003
5. ### CBFalconerGuest

Adding the constant expression clause may be the rub, as offhand I
do not know of any way of evaluating n above. Well, possibly a
table, such as:

#if INT_MAX == 32767
# define n 16
#elif INT_MAX == 65536
# define n 17
.....

which doesn't appear overly attractive to me.

Apropos to other arguments going on around here, things might have
been simpler if the maximum bit weight (n above) had been
specified as an exponent of two, rather than the <T>_MAX values.
i.e.

#define INT_MAX_BIT 30

etc. This also leaves no holes and ambiguity to foster arguments

CBFalconer, Nov 24, 2003
6. ### Dan PopGuest

And doesn't appear correct at all to me. Are you sure you're familiar
with the powers of two? ;-)

BTW, if you go this way, you can define the square root directly, instead
of n.

Dan

Dan Pop, Nov 25, 2003
7. ### CBFalconerGuest

0.0002% is well within the expected experimental error

CBFalconer, Nov 26, 2003
8. ### Dan PopGuest

Still missing the point. Your worst error above is 6.66% ;-)

Dan

Dan Pop, Nov 26, 2003
9. ### Dave ThompsonGuest

In general yes, though not if you are running the loop upwards (as was
the previous-post case) and n is not almost UINT_MAX (which caveat I
didn't state). But you can add a check for v <= sqrt_of_uint_max,
which is actually a compile-time constant although it seems difficult
to portably write it so, and I bet it's still faster than divide.

- David.Thompson1 at worldnet.att.net

Dave Thompson, Nov 27, 2003
10. ### James HuGuest

I don't doubt multiplication is faster than division on most platforms.
But, I tend to first write code that I know will work first. I've been
bitten by multiplication overflow too many times, I'm afraid.

-- James

James Hu, Nov 27, 2003
11. ### Paul HsiehGuest

Paul Hsieh, Nov 28, 2003
12. ### Eric SosmanGuest

If you're using the `%' operator to check a candidate
for divisibility, there's an excellent chance that the
`/' to check for end-of-range is "free."

for (div = 3; number / div >= div; div += 2)
if (number % div == 0)
...

Many compilers will perform just one division to generate
both the quotient and the remainder.

Eric Sosman, Dec 1, 2003
13. ### Ben PfaffGuest

In case it isn't smart enough, you can encourage it by using the
standard C library div() function.

Ben Pfaff, Dec 1, 2003
14. ### NaomiD

Joined:
Jul 22, 2009
Messages:
1
0
Prime number algorithm in C++

#include <iostream>
using namespace std;

void findPrime(int n)
{

int i,j;
int nn = n+1;
bool array[nn];
array[0] = false;
array[1] = false;
for (i=2; i<nn; i++)
{
array = true;
}
for(i=2; i<nn; i++)
{

for (j=2; (i*j)<nn; j++)
{
array[i*j] = false;
}
}

for(i=0; i<nn; i++)
{
if(array)
{
cout<<i<<" is prime";
cout<<endl;
}
}

}

int main()
{

int n = 100;
findPrime(n);

}

works for me!

NaomiD, Jul 22, 2009