Fastest algorithm for primality test [closed]

One good method is the Miller-Rabin test. It should be noted however, that this is only a probabilistic test.

A Miller-Rabin test to the seven bases 2, 325, 9375, 28178, 450775, 9780504, 1795265022 has been proved by Jim Sinclair to deterministically test if a number less than 2^64 is prime. See http://miller-rabin.appspot.com/.

I believe that the asymptotically fastest current (non-probabilistic) primality test is the "Lenstra/Pomerance improved AKS", which has complexity that is essentially O(n^6).

However, the range of long long (assuming a typical system where that is a 64 bit integer) is not really that big. In particular, there are only ~200 million primes less than 2^32, so using a fast probabilistic test, followed by trial division with a precomputed list of primes (or just looking the number up in a list of primes, if you have one) would be pretty darn fast in that range, and is probably the right way to go about it.

I would suggest the GNU MP library that uses the Miller-Rabin algorithm. I have used it for a few months and it's very fast.

Specifically, the function mpz_probab_prime_p does this, you can also use another function mpz_nextprime to find the next prime number greater than a number. I can post code samples if you would like.

I came up with a really good algorithm, that is much faster than checking all the divisors - which of course also lets me crack public key encryption.

Hang on - I just need to close the window, there are all these black helicopters overhead ........

(Or look at How can I test for primality?)