- A. O. L. Atkin and D. J. Bernstein, "Prime Sieves Using Binary Quadratic Forms", in Mathematics of Computation, vol. 73, no. 246, pp. 1023–1030.
- D. J. Bernstein, primegen 0.97.
A fast prime generator. I have implemented the technique described by Atkin and Bernstein (as opposed to brute-forcing quadratic congruences). While Bernstein has already provided an optimised implementation, I found the code very hard to understand, and it does not store the list of primes, so I decided to write it myself.
Also included here is a wheel-factorised sieve of Eratosthenes implementation which proceeds mostly along the same lines as the sieve of Atkin.
Both sieves start generating primes from 7 onwards. The first three primes (i.e. 2, 3 and 5) must be handled separately.
The sieve of Atkin is faster than the sieve of Eratosthenes. Tabulated below are the times taken (to two significant figures) to construct the sieves up to n on my machine. Note that the time taken to iterate over the primes (after constructing the sieves) will, in theory, be identical for a given n because the two sieves store the list of primes in the same manner.
| n | Eratosthenes | Atkin |
|---|---|---|
| 216 | 0 ms | 0 ms |
| 217 | 0 ms | 0 ms |
| 218 | 1 ms | 0 ms |
| 219 | 2 ms | 0 ms |
| 220 | 4 ms | 0 ms |
| 221 | 7 ms | 1 ms |
| 222 | 16 ms | 3 ms |
| 223 | 32 ms | 6 ms |
| 224 | 69 ms | 11 ms |
| 225 | 140 ms | 25 ms |
| 226 | 300 ms | 50 ms |
| 227 | 680 ms | 210 ms |
| 228 | 1800 ms | 560 ms |
| 229 | 3900 ms | 1400 ms |
| 230 | 8700 ms | 3000 ms |
I rewrote this sieve of Atkin implementation in Rust to augment my Project Euler solutions library.