Sieve of Atkin

Sieve of Atkin

In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers 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. BernsteinA.O.L. Atkin, D.J. Bernstein, [http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf "Prime sieves using binary quadratic forms"] , Math. Comp. 73 (2004), 1023-1030.] .

Algorithm

In the algorithm:
* All remainders are modulo-sixty remainders (divide the number by sixty and return the remainder).
* 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 whole number; all entries of this list should initially be marked nonprime.
# For each entry in the sieve list :
#* If the entry is for a number with remainder 1, 13, 17, 29, 37, 41, 49, or 53, flip it for each possible solution to 4"x"2 + "y"2 = "entry_number".
#* If the entry is for a number with remainder 7, 19, 31, or 43, flip it for each possible solution to 3"x"2 + "y"2 = "entry_number".
#* If the entry is for a number with remainder 11, 23, 47, or 59, flip it for each possible solution to 3"x"2 - "y"2 = "entry_number" when "x" > "y".
#* If the entry has some other remainder, 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.

Pseudocode

The following is pseudocode for a straightforward version of the algorithm:

// arbitrary search limitlimit ← 1000000

// initialize the sieveis_prime(i) ← false, i ∈ [5, limit]

// put in candidate primes: // integers which have an odd number of// representations by certain quadratic formsfor (x, y) in [1, √limit] × [1, √limit] : n ← 4x²+y² if (n ≤ limit) ∧ (n mod 12 = 1 ∨ n mod 12 = 5): is_prime(n) ← ¬is_prime(n) n ← 3x²+y² if (n ≤ limit) ∧ (n mod 12 = 7): is_prime(n) ← ¬is_prime(n) n ← 3x²-y² if (x > y) ∧ (n ≤ limit) ∧ (n mod 12 = 11): is_prime(n) ← ¬is_prime(n) // eliminate composites by sievingfor 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, 3for 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 modulo-sixty remainder 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, or 58 are divisible by two and not prime. All numbers with modulo-sixty remainder 3, 9, 15, 21, 27, 33, 39, 45, 51, or 57 are divisible by three and not prime. All numbers with modulo-sixty remainder 5, 25, 35, or 55 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 the number of solutions to 4"x"2 + "y"2 = "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 3"x"2 + "y"2 = "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 3"x"2 − "y"2 = "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 O("N"/log log "N") operations with only "N"1/2+o(1) bits of memory. That is a little better than the sieve of Eratosthenes which uses O("N") operations and O("N"1/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.

Addendum

The first two equations used to determine if a number is prime after their respective modulo tests are equations for ellipses. They can be rewritten into standard form for an ellipse by dividing both sides of the equation by "n", where "n" is the entry number being tested for primality. Using the equations in this form is easier to implement a test for various reasons. See ellipse for more information.

References

External links

* [http://cr.yp.to/primegen.html An optimized implementation of the sieve] (in C)
* [http://krenzel.info/?p=83 Python implementation]


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Sieve of Eratosthenes — Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime s square). In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple,… …   Wikipedia

  • A. O. L. Atkin — Arthur Oliver Lonsdale Atkin (July 31, 1925 – December 28, 2008), 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 …   Wikipedia

  • Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… …   Wikipedia

  • General number field sieve — In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 100 digits. Heuristically, its complexity for factoring an integer n (consisting of log2 n bits) is of …   Wikipedia

  • Generating primes — In mathematics, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public key cryptography, and search of prime factors in large numbers.For relatively… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) 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… …   Wikipedia

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

  • Discrete logarithm — In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga(b) is a solution of the equation ax = b over the… …   Wikipedia

  • Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”