OJ Board

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]

Depends on how big n is...

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

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]

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)..

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

Keep posting!

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

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

Keep posting!

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