The sieve of Atkin is a sieve for generating prime numbers up to a given bound using representations of integers by binary quadratic forms. Unlike the sieve of Eratosthenes, which removes multiples of primes, it tests the parity of representation counts and removes multiples of squares of primes (Atkin and Bernstein 2004).
For a squarefree integer 
relatively
prime to 6, the appropriate representation test depends on its residue
class modulo 12. If 
,
count solutions of 
with positive integers 
and 
. If 
, count solutions of 
with positive integers 
and 
. If 
, count solutions of 
with integers 
. In each case, 
is prime iff
the count is odd (Atkin and Bernstein 2004).
To form a sieve, candidate flags are toggled for each representation and candidates divisible by a square of a prime are
then removed. The primes 2 and 3 are included separately.
Atkin and Bernstein (2004) gave an optimized implementation using 
operations on 
-bit integers and 
bits of working memory to generate the primes
up to 
.
These bounds apply to their optimized algorithm, not
to an arbitrary implementation of the representation tests.
