Sieve of Atkin

In mathematics, the Sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient Sieve of Eratosthenes. It was created by A. O. L. Atkin and Daniel J. BernsteinTemplate:Fn.

Algorithm

First, write four things :

• A list to hold primes you've found. It starts out filled with the prime numbers below sixty.
• Three lists to hold numbers that remain to be checked and have certain remainders when divided by sixty. They start out filled with all integers from sixty up to the last number you care about, as long as they fit the remainders in one of these classes (notice that numbers with some remainders are ignored completely) :
  1. Remainders of 1, 13, 17, 29, 37, 41, 49, or 53.
  2. Remainders of 7, 19, 31, or 43.
  3. Remainders of 11, 23, 47, or 59.

Then, for each remaining number, n :

• In class one, count the number of combinations of x > 0 and y > 0 that are solutions to 4x² + y² = n.
• In class two, count the number of combinations of x > 0 and y > 0 that are solutions to 3x² + y² = n.
• In class three, count the number of combinations of x > 0 and y > 0 that are solutions to 3x² - y² = n.
• If the count was even, delete the number from the list.

Then, we perform the Sieve of Eratosthenes with a small modification :

• For each prime seven or higher, delete all multiples of the prime squared.

Finally, move the remaining numbers to the list of primes.

References

Template:Fnb A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030.

External links

• The sieve in optimized C