Prime Number

[_.B._]

Greetings!
Which is the fastest way to find if a number is Prime?
My algorithm, brought from Pascal, is this:

[cpp]bool Prime(unsigned long n)
{ unsigned long Con = 1,Max = sqrt(n);
if (n < 2)
return false;
while ((Max > 1) && (Con < 2))
{ if (n % Max == 0)
Con++;
Max--;
}
return Con == 1;
}
[/cpp]

[UFP2161]

Depends on how big n is...

[_.B._]

Let's say the classical 1 to 1,000,000, or for 1 to 10,000,000.
No bigger than 10,000,000.

[Minilek]

why mod by even things ? just check mod by 2 in the beginning then you can speed things up by a factor of 2.

[c]
int i;
if (n<2) return 0;
else if (!(n&1)) return n==2;
else {
for (i=3;i*i<=n;i+=2) if (!(n%i)) return 0;
return 1;
}

[/c]

[UFP2161]

Also depends on how many numbers you want to check of primeness.. if just a few, the simple check all numbers up to sqrt(n) is probably fastest..

If you need to do it a lot more times, then sieving up to 10,000,000 and using a O(1) lookup is probably faster..

If the numbers are even higher than that, then you'd need to look up some more general primality tests (which will determine strong probable primes [i.e. is prime with xx% certainty], and may still not be necessarily prime, depending on how the particular test works)..

[_.B._]

Thanks to both of you!
I'll consider it all

Keep posting!

[Per]

IMO, the best algorithm is Miller-Rabin (though of course, it depends on application. If you need to check if every element from 1 to n is prime, you should use a sieve, but if n is at least, say, a few millions, and n is much larger than the number of queries, I would recommend Miller-Rabin).

http://www.google.com/search?q=miller-rabin

[_.B._]

Greetings Per!
Thanks, I'll have to check for that too.

Keep posting!

[Larry]

If you want to see implementations, I recommend a look at Java's BigInteger class (the source).