Fast prime finder??

[Namir]

(08-01-2016 09:59 PM)ttw Wrote:  There are really no formulas for primes. The primes seem to occur at random (with a known density of ln(N)/N for the number of primes up to N). One can do clever sieving and use some pseudo-prime tests (like Fermat's) to check.

For searching (not on calculators), I've often used a storage of 30 numbers in 8 bits. Checking all numbers not divisible by 30, one get that primes have remainder of (1,7,11,13,17,18,23,29). I pack 30 numbers into one byte and set the appropriate bit if that number is prime. One can go higher with more complicated packing. This is still linear. One can do a bit better.

A more efficient packing is to store the difference between primes as primes get large. This is a bit complicated.

None of this tells whether a number is prime, but most prime checking methods work better with a bunch of stored primes.

https://en.wikipedia.org/wiki/Primality_test gives some methods.

Thanks ttw for the link. That Wikipedia page has p-code that seems to be a very good prime tester, compared to the few other similar functions I have found so far.

Namir