Sieve of Atkin

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. In the algorithm: All remainders are modulo-sixty remainders (divide the number by 60 and return the remainder). All numbers, including x and y, 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 n in the sieve list, with modulo-sixty remainder r : If r is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to 4x2 + y2 = n. The number of flipping operations as a ratio to the sieving range for this step approaches 4/15 × 8/60 (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 r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x2 + y2 = n. The number of flipping operations as a ratio to the sieving range for this step approaches π × 4/60 (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....