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.
The following is pseudocode which combines Atkin's algorithms 3.1, 3.2, and 3.3[1] 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.
A special modified "enumerating lattice points" variation which is not the above version of the sieve of Atkin can theoretically compute primes up to N using O(N / log(log(N))) operations with N1/2+o(1) bits of memory,[1] but this variation is rarely implemented.
[3][4][5] Pritchard observed that for the wheel sieves, one can reduce memory consumption while preserving Big-O time complexity, but this generally comes at a cost in an increased constant factor for time per operation due to the extra complexity.