In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, the sieve of Atkin does some preliminary work and then marks off multiples of squares of primes, thus achieving a better theoretical asymptotic complexity. It was created in 2003 by A. O. L. Atkin and Daniel J. Bernstein.
Algorithm
In the algorithm: All remainders are modulo-sixty remainders (divide the number by 60 and return the remainder). All numbers, including and , are positive integers. Flipping an entry in the sieve list means to change the marking (prime or nonprime) to the opposite marking. This results in numbers with an odd number of solutions to the corresponding equation being potentially prime (prime if they are also square free), and numbers with an even number of solutions being composite.
The algorithm: Create a results list, filled with 2, 3, and 5. Create a sieve list with an entry for each positive integer; all entries of this list should initially be marked non prime (composite). For each entry number in the sieve list, with modulo-sixty remainder : If is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to . The number of flipping operations as a ratio to the sieving range for this step approaches × (the "8" in the fraction comes from the eight modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.1117010721276.... If is 7, 19, 31, or 43, flip the entry for each possible solution to . The number of flipping operations as a ratio to the sieving range for this step approaches × (the "4" in the fraction comes from the four modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.072551974569.... If is 11, 23, 47, or 59, flip the entry for each possible solution to when . The number of flipping operations as a ratio to the sieving range for this step approaches × (the "4" in the fraction comes from the four modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.060827679704.... If is something else, ignore it completely. Start with the lowest number in the sieve list. Take the next number in the sieve list still marked prime. Include the number in the results list. Square the number and mark all multiples of that square as non prime. Note that the multiples that can be factored by 2, 3, or 5 need not be marked, as these will be ignored in the final enumeration of primes. Repeat steps four through seven. The total number of operations for these repetitions of marking the squares of primes as a ratio of the sieving range is the sum of the inverse of the primes squared, which approaches the prime zeta function(2) of 0.45224752004... minus , , and for those primes which have been eliminated by the wheel, with the result multiplied by for the ratio of wheel hits per range; this results in a ratio of about 0.01363637571....
Adding the above ratios of operations together, the above algorithm takes a constant ratio of flipping/marking operations to the sieving range of about 0.2587171021...; From an actual implementation of the algorithm, the ratio is about 0.25 for sieving ranges as low as 67.
Pseudocode
The following is pseudocode which combines Atkin's algorithms 3.1, 3.2, and 3.3 by using a combined set "s" 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 x's/y'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