World Library  
Flag as Inappropriate
Email this Article

Sieve of Atkin

Article Id: WHEBN0002150920
Reproduction Date:

Title: Sieve of Atkin  
Author: World Heritage Encyclopedia
Language: English
Subject: Sieve of Sundaram, List of algorithms, Pocklington primality test, Pocklington's algorithm, Cornacchia's algorithm
Collection: Articles with Example Pseudocode, Primality Tests
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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 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 2004 by A. O. L. Atkin and Daniel J. Bernstein.[1]

Contents

  • Algorithm 1
  • Pseudocode 2
  • Explanation 3
  • Computational complexity 4
  • See also 5
  • References 6
  • External links 7

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 positive integers.
  • Flipping an entry in the sieve list means to change the marking (prime or nonprime) to the opposite marking.
  1. Create a results list, filled with 2, 3, and 5.
  2. Create a sieve list with an entry for each positive integer; all entries of this list should initially be marked nonprime (composite).
  3. 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.
  4. Start with the lowest number in the sieve list.
  5. Take the next number in the sieve list still marked prime.
  6. Include the number in the results list.
  7. Square the number and mark all multiples of that square as nonprime.
  8. 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.

With the equations in this algorithm, x and y range over the positive integers.

Pseudocode

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

// arbitrary search limit
limit ← 1000000         

// initialize the sieve
for i in [5, limit]: is_prime(i) ← false

// 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
        for k in {n², 2n², 3n², ..., limit}:
            is_prime(k) ← false

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 with remainder modulo 60 that is divisible by two, three, or five, since numbers with a modulo 60 remainder divisible by one of these three primes are themselves divisible by that prime.

All numbers n 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[1]).

All numbers n 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[1]).

All numbers n 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 3x2y2 = n is odd and the number is squarefree (proven as theorem 6.3 of[1]).

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 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.[1] These asymptotic computational complexities include simple optimizations, such as wheel factorization, and splitting the computation to smaller blocks.

See also

References

  1. ^ a b c d e A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030.[1]

External links

  • An optimized implementation of the sieve (in C)
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.