Maciej A. Czyzewski Blog Talks About

# Sieve of Atkin, finding prime numbers faster

Posted on

It 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.