11–20 of 35 posts
there are also very fast primality tests that work statistically. It's called Miller-Rabin, I tested in the browser here[1] and it can do them all in about three minutes on my phone. [1] https://claude.ai/public/artifacts/baa198ed-5a17-4d04-8cef-7...
What are the false positive/negative rates?
Earlier quoted context omitted.
What are the false positive/negative rates?
for the way this one was done, this witness set has been proven to produce no false positives or negatives for n < 2³⁷.
The largest three primes it can show are
3317044064679887385961783
3317044064679887385961801
3317044064679887385961813
So essentially it can test all 81-bit integers and some 82-bit integers for primality. It does so using the Miller-Rabin primality test with prime bases derived from https://oeis.org/A014233 (OEIS A014233). The algorithm is implemented in about 80 lines of plain JavaScript. If you view the source, look for the function isPrimeByMR.
The Miller-Rabin test is inherently probabilistic. It tests whether a number is a probable prime by checking whether certain number theoretic congruence relations hold for a given base a. The test can yield false positives, that is, a composite number may pass the test. But it cannot have false negatives, so a number that fails the test is definitely composite. The more bases for which the test holds, the more likely it is that the tested number is prime. It has been computationally verified that there are no false positives below 3317044064679887385961981 when tested with prime bases 2, 3, 5, ..., 41. So although the algorithm is probabilistic, it functions as a deterministic test for all numbers below this bound when tested with these 13 bases.
There is also the segmented Sieve of Eratosthenes. It has a simlar performance but uses much less memory: the number of prime numbers from 2 to sqrt(n). For example, for n = 1000000, the RAM has to store only 168 additional numbers. I use this algorithm here https://surenenfiajyan.github.io/prime-explorer/
n = 1000000 # must be even
sieve = [True] * (n/2)
for i in range(3,int(n**0.5)+1,2):
if sieve[i/2]: sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
…
# x is prime if x%2 and sieve[x/2]
Why include writing the primes to a file instead of, say, standard output? That increases the optimization space drastically and the IO will eclipse all the careful bitwise math Does having the primes in a file even allow faster is-prime lookup of a number?
You can combine the Sieve and Wheel techniques to reduce the memory requirements dramatically. There's no need to use a bit for numbers that you already know can't be prime. You can find a Python implementation at https://stackoverflow.com/a/62919243/5987
There is also the segmented Sieve of Eratosthenes. It has a simlar performance but uses much less memory: the number of prime numbers from 2 to sqrt(n). For example, for n = 1000000, the RAM has to store only 168 additional numbers. I use this algorithm here https://surenenfiajyan.github.io/prime-explorer/