Sieve of Atkin
Encyclopedia
In mathematics
, the sieve of Atkin is a fast, modern algorithm
for finding all prime number
s up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes
, but does some preliminary work and then marks off multiples of primes squared, rather than multiples of primes. It was created by A. O. L. Atkin
and Daniel J. Bernstein
.
for a straightforward version of the algorithm
:
This pseudocode is written for clarity. Repeated and wasteful calculations mean that it would run slower than the sieve of Eratosthenes. To improve its efficiency, faster methods must be used to find solutions to the three quadratics. At the least, separate loops could have tighter limits than [1, √limit].
All numbers with modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1. These numbers are prime if and only if
the number of solutions to 4x2 + y2 = n is odd and the number is squarefree
(proven as theorem 6.1 of).
All numbers with modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime if and only if the number of solutions to 3x2 + y2 = n is odd and the number is squarefree (proven as theorem 6.2 of).
All numbers with modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only if the number of solutions to 3x2 − y2 = n is odd and the number is squarefree (proven as theorem 6.3 of).
None of the potential primes are divisible by 2, 3, or 5, so they can't be divisible by their squares. This is why squarefree checks don't include 22, 32, and 52.
(N/log log N) operations with only N1/2 + o(1) bits of memory. That is a little better than the sieve of Eratosthenes which uses O(N) operations and O(N1/2(log log N)/log N) bits of memory. These asymptotic computational complexities
include simple optimizations, such as wheel factorization
, and splitting the computation to smaller blocks.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the sieve of Atkin is a fast, modern algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for finding all prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
, but does some preliminary work and then marks off multiples of primes squared, rather than multiples of primes. It was created by A. O. L. Atkin
A. O. L. Atkin
Arthur Oliver Lonsdale Atkin , who published under the name A. O. L. Atkin, was a Professor Emeritus of mathematics at the University of Illinois at Chicago. As an undergraduate during World War II, he worked at Bletchley Park cracking German codes. He received his Ph.D...
and Daniel J. Bernstein
Daniel J. Bernstein
Daniel Julius Bernstein is a mathematician, cryptologist, programmer, and professor of mathematics at the University of Illinois at Chicago...
.
Algorithm
In the algorithm:- All remainders are modulo-sixty remainders (divide the number by sixty and return the remainderRemainderIn arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....
). - All numbers, including x and y, are whole numbers (positive integers).
- Flipping an entry in the sieve list means to change the marking (prime or nonprime) to the opposite marking.
- 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 nonprime.
- 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.
- If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x2 + y2 = n.
- If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x2 − y2 = n when x > y.
- 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 prime.
- Include the number in the results list.
- Square the number and mark all multiples of that square as nonprime.
- Repeat steps five through eight.
- This results in numbers with an odd number of solutions to the corresponding equation being prime, and an even number being nonprime.
Pseudocode
The following is pseudocodePseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
for a straightforward version of the algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
:
// arbitrary search limit
limit ← 1000000
// initialize the sieve
is_prime(i) ← false, ∀ i ∈ [5, limit]
// put in candidate primes:
// integers which have an odd number of
// representations by certain quadratic forms
for (x, y) in [1, √limit] × [1, √limit]:
n ← 4x²+y²
if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5):
is_prime(n) ← ¬is_prime(n)
n ← 3x²+y²
if (n ≤ limit) and (n mod 12 = 7):
is_prime(n) ← ¬is_prime(n)
n ← 3x²-y²
if (x > y) and (n ≤ limit) and (n mod 12 = 11):
is_prime(n) ← ¬is_prime(n)
// eliminate composites by sieving
for n in [5, √limit]:
if is_prime(n):
// n is prime, omit multiples of its square; this is
// sufficient because composites which managed to get
// on the list cannot be square-free
is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit}
print 2, 3
for n in [5, limit]:
if is_prime(n): print n
This pseudocode is written for clarity. Repeated and wasteful calculations mean that it would run slower than the sieve of Eratosthenes. To improve its efficiency, faster methods must be used to find solutions to the three quadratics. At the least, separate loops could have tighter limits than [1, √limit].
Explanation
The algorithm completely ignores any numbers divisible by two, three, or five. All numbers with an even modulo-sixty remainder are divisible by two and not prime. All numbers with modulo-sixty remainder divisible by three are also divisible by three and not prime. All numbers with modulo-sixty remainder divisible by five are divisible by five and not prime. All these remainders are ignored.All numbers with modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1. These numbers are prime if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
the number of solutions to 4x2 + y2 = n is odd and the number is squarefree
Square-free integer
In mathematics, a square-free, or quadratfrei, integer is one divisible by no perfect square, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32...
(proven as theorem 6.1 of).
All numbers with modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime if and only if the number of solutions to 3x2 + y2 = n is odd and the number is squarefree (proven as theorem 6.2 of).
All numbers with modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only if the number of solutions to 3x2 − y2 = n is odd and the number is squarefree (proven as theorem 6.3 of).
None of the potential primes are divisible by 2, 3, or 5, so they can't be divisible by their squares. This is why squarefree checks don't include 22, 32, and 52.
Computational complexity
This sieve computes primes up to N using OBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(N/log log N) operations with only N1/2 + o(1) bits of memory. That is a little better than the sieve of Eratosthenes which uses O(N) operations and O(N1/2(log log N)/log N) bits of memory. These asymptotic computational complexities
Asymptotic computational complexity
In computational complexity theory, asymptotic computational complexity is the usage of the asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O notation....
include simple optimizations, such as wheel factorization
Wheel factorization
Wheel factorization is a graphical method for manually performing a preliminary to the Sieve of Eratosthenes that separates prime numbers from composites. Start by writing the natural numbers around circles as shown below. Prime numbers in the innermost circle have their multiples in similar...
, and splitting the computation to smaller blocks.
External links
- An optimized implementation of the sieve (in CC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
)