# Sieve of Atkin, finding prime numbers faster

Posted onIt is an optimized version of the ancient **sieve of Eratosthenes** which 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 2003 by *A. O. L. Atkin* and *Daniel J. Bernstein*. References can be found in “Prime sieves using binary quadratic forms.”

## Complexity

The page segmented version implemented by the authors has the same $O(N)$ operations but reduces the memory requirement to just that required by the base primes below the square root of the range of $O(N^{1/2} / \log N)$ bits of memory plus a minimal page buffer.

## Optimization

All numbers with a modulo-sixty remainder:

- that is divisible by 2, 3, or 5 are not prime because they are divisible by 2, 3, or 5, respectively.
- 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1. These numbers are prime iff the number of solutions to $4x^{2} + y^{2} = n$ is odd and the number is not a square of another integer.
- 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime iff the number of solutions to $3x^{2} + y^{2} = n$ is odd and the number is not a square of another integer.
- 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime iff the number solutions to $3x^{2} - y^{2} = n$ is odd and the number is not a square of another integer.