Generating All 32-Bit Primes (Part I)

My little Prime Grid tool at <https://susam.net/primegrid.html> can display all primes less than 3317044064679887385961981 (an 82-bit number).

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 Miller-Rabin primality test with prime bases drawn from https://oeis.org/A014233 to determine whether a number is prime.

Here is the complete implementation of the algorithm: <https://github.com/susam/susam.net/blob/0.6.0/content/tree/p...>

I also have a JavaScript speed test that compares the wall-clock time for testing primes using naive trial division and Miller-Rabin here: <https://susam.net/code/web/miller-rabin-speed-test.html>

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/

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

If you take all 53 8 bit primes, you can use modular arithmetic with a residue base to work with numbers up to

64266330917908644872330635228106713310880186591609208114244758680898150367880703152525200743234420230

This would require 334 bits.

Do you know the https://en.wikipedia.org/wiki/Sieve_of_Atkin? It's mind-blowing.

This got me through many of the first 100 problems on Project Euler:

    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]

I always like seeing implementations that start from trial division and gradually introduce optimizations like wheel factorization.

It makes the trade-offs much clearer than jumping straight to a complex sieve.

Very well written

> There is a long way to go from here. Kim Walisch's primesieve can generate all 32-bit primes in 0.061s (though this is without writing them to a file)

Oh, come on, just use a bash indirection and be done with it. It takes 1 minute and you had another result for comparison

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?

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

[dead]

[dead]