Name
• Prime numbers
Edit
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 Eratostheneswhich does some preliminary work and then marks off multiples of the square of each prime, rather than multiples of the prime itself. It was created in 2004 by A. O. L. Atkin andDaniel J. Bernstein.

Algorithm

In the algorithm:

• All remainders are modulo-sixty remainders (divide the number by sixty 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.
1. Create a results list, filled with 2, 3, and 5.
2. Create a sieve list with an entry for each positive integer; all entries of this list should initially be marked nonprime (composite).
3. 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.
• If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x2 + y2 = n.
• If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x2 − y2 = n when x > y.
• If r is something else, ignore it completely.