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]

## Prime Number

**Moderator:** Board moderators

### Prime Number

**_.**

### Up to 10,000,000

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

No bigger than 10,000,000.

No bigger than 10,000,000.

**_.**

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

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