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 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 π√0.12 × 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.... If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x2 − y2 = n when x > y. The number of flipping operations as a ratio to the sieving range for this step approaches √1.92ln(√0.5+√1.5) × 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.060827679704.... 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 as being 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 4 through 7. 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 at 2 (equal to 0.45224752004...) minus 1/22 , 1/32, and 1/52 for those primes which have been eliminated by the wheel, with the result multiplied by 16/60 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 xs and ys 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):
This pseudocode is written for clarity; although some redundant computations have been eliminated by controlling the odd/even x/y combinations, it still wastes almost half of its quadratic computations on non-productive loops that do not pass the modulo tests, so it will not be faster than an equivalent wheel-factorized (2/3/5) sieve of Eratosthenes. To improve its efficiency, a method must be devised to minimize or eliminate these non-productive computations.
Implementation Below is an implementation of the algorithm within Java. This makes use of a boolean array to mark integers as being prime, or not. Note that while the above implementation is true to the intent of the Atkin algorithm, it is not an example showing the true computational complexity of the algorithm due to many redundant operations above as described by the algorithm - note that `25 + 60k` and `55 + 60k` where `k` is all non-negative integers fall through the modulo tests for a constant factor increase in the number of operations although these errors are compensated for by running the squares-free operation from multiples of 5 rather than the 7 as would be used by the true algorithm for an increase above a constant factor. Worse, the `x` and `y` values are allowed to range up to the limit value rather than limiting them to values less than the limit by large factors resulting a huge increase in computational complexity for redundant operations that do not contribute to the result. For these reasons, the above implementation does not show the `O(n)` asymptotic computational complexity of which the algorithm is capable and is not true to the pseudo code above.
… excerpt ends here. Continue reading the full article.
