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.
- 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 nonprime (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.
- 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.
- 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 nonprime.
- Repeat steps five through eight.
- This results in numbers with an odd number of solutions to the corresponding equation being prime, and an even number being nonprime.
Read more about this topic: Sieve Of Atkin