The following is
pseudocode which
combines Atkin's algorithms 3.1, 3.2, and 3.3 by using a
combined set of all the numbers modulo 60 excluding those which are multiples of the prime numbers 2, 3, and 5, as per the algorithms, for a straightforward version of the
algorithm that supports optional bit-packing of the wheel; although not specifically mentioned in the referenced paper, this pseudocode eliminates some obvious combinations of odd/even s and s in order to reduce computation where those computations would never pass the modulo tests anyway (i.e. would produce even numbers, or multiples of 3 or 5): limit ← 1000000000 // arbitrary search limit // set of wheel "hit" positions for a 2/3/5 wheel rolled twice as per the Atkin algorithm s ← {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59} // Initialize the sieve with enough wheels to include limit: for n ← 60 × w + x where w ∈ {0,1,...,limit ÷ 60}, x ∈ s: is_prime(n) ← false // Put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms. // Algorithm step 3.1: for n ≤ limit, n ← 4x²+y² where x ∈ {1,2,...} and y ∈ {1,3,...} // all x's and only odd y's if n mod 60 ∈ {1,13,17,29,37,41,49,53}: is_prime(n) ← ¬is_prime(n) // toggle state // Algorithm step 3.2: for n ≤ limit, n ← 3x²+y² where x ∈ {1,3,...} and y ∈ {2,4,...} // only odd x's if n mod 60 ∈ {7,19,31,43}: // and even y's is_prime(n) ← ¬is_prime(n) // toggle state // Algorithm step 3.3: for n ≤ limit, n ← 3x²-y² where x ∈ {2,3,...} and y ∈ {x-1,x-3,...,1} //all even/odd if n mod 60 ∈ {11,23,47,59}: // odd/even combos is_prime(n) ← ¬is_prime(n) // toggle state // Eliminate composites by sieving, only for those occurrences on the wheel: for n² ≤ limit, n ← 60 × w + x where w ∈ {0,1,...}, x ∈ s, n ≥ 7: if is_prime(n): // n is prime, omit multiples of its square; this is sufficient // because square-free composites can't get on this list for c ≤ limit, c ← n² × (60 × w + x) where w ∈ {0,1,...}, x ∈ s: is_prime(c) ← false // one sweep to produce a sequential list of primes up to limit: output 2, 3, 5 for 7 ≤ n ≤ limit, n ← 60 × w + x where w ∈ {0,1,...}, x ∈ s: if is_prime(n): output n This pseudocode is written for clarity; although some redundant computations have been eliminated by controlling the odd/even / combinations, it still wastes almost half of its quadratic computations on non-productive loops that do not pass the modulo tests, so it will not be faster than an equivalent
wheel-factorized (2/3/5)
sieve of Eratosthenes. To improve its efficiency, a method must be devised to minimize or eliminate these non-productive computations. == Implementation ==