Fast prime finder??

[Claudio L.]

(07-28-2016 08:22 PM)Namir Wrote:  Hi All,

I am looking for the fastest algorithm to:

1) Determine if a number is a prime.
2) Find the next prime after a given number.

I plan to include the best answer in my HHC2016 presentation.

The keyword here is fast computational-wise.

Thanks!

Namir

This problem has been studied a lot, and the algorithms are well known. I'm not sure what you are aiming at: calculator code? any code? or just the algorithm? what magnitude of numbers do you need to test?
I wrote a few routines for newRPL that use a bitmap table for primes <120000. This allows you to both test for primality and get the next prime number (given a number <120000) extremely fast, which speeds up the brute force primality test for numbers up to 120000^2 = 1.44e10.
For larger numbers it falls back to brute force (test the remainder after division by every prime <= sqrt(N)).
In the future it will use Miller-Rabin or similar pseudo-prime algorithm for large numbers, but that's not implemented yet.

I recently tested the number 9,999,999,967 per this thread:
http://www.hpmuseum.org/forum/thread-6567.html

Since it's < 1.44e10 I got a very fast result at 0.057s.

While the tables are encoded in a creative way, there's nothing to be proud of, as it's basically a brute force primality test accelerated with look-up tables.