Sieve of Atkin

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

Algorithm[edit]

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 non prime (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. The number of flipping operations as a ratio to the sieving range for this step approaches 4π/15[1] × 8/60 (the "8" in the fraction comes from the eight modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.1117010721276....
    • If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x2 + y2 = n. The number of flipping operations as a ratio to the sieving range for this step approaches π0.12[1] × 4/60 (the "4" in the fraction comes from the four modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.072551974569....
    • If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x2 − y2 = n when x > y. The number of flipping operations as a ratio to the sieving range for this step approaches 1.92ln(0.5+1.5)[1] × 4/60 (the "4" in the fraction comes from the four modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.060827679704....
  4. If r is something else, ignore it completely.
  5. Start with the lowest number in the sieve list.
  6. Take the next number in the sieve list still marked prime.
  7. Include the number in the results list.
  8. Square the number and mark all multiples of that square as non prime. Note that the multiples that can be factored by 2, 3, or 5 need not be marked, as these will be ignored in the final enumeration of primes.
  9. Repeat steps five through eight. The total number of operations for these repetitions of marking the squares of primes as a ratio of the sieving range is the sum of the inverse of the primes squared, which approaches the Prime Zeta Function(2) of 0.45224752004... minus 1/22, 1/32, and 1/52 for those primes which have been eliminated by the wheel, with the result multiplied by 16/60 for the ratio of wheel hits per range; this results in a ratio of about 0.01363637571....
  • This results in numbers with an odd number of solutions to the corresponding equation being prime, and an even number being non prime.

Adding the above ratios of operations together, the above algorithm takes a constant ratio of flipping/marking operations to the sieving range of about 0.2587171021...; From an actual implementation of the algorithm, the ratio is about 0.25 for sieving ranges as low as 67.

Pseudocode[edit]

The following is pseudocode for a straightforward version of the algorithm that supports bit packing of the wheel:

limit ← 1000000000        // arbitrary search limit

//the set of wheel positions for a 2/3/5 wheel
s ∈ {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61}

// Initialize the sieve in even wheels to include limit
for n where n ← 60 × w + x where w ∈ {0,...(limit - 7) ÷ 60}, x in s:
    is_prime(n) ← false

// Put in candidate primes:
// integers which have an odd number of
// representations by certain quadratic forms.
for n ≤ limit, n ← 4x²+y² where x ∈ {1,2,...} and y ∈ {1,3,...} // all x's odd y's
    if n mod 60 ∈ {1,13,17,29,37,41,49,53}:
        is_prime(n) ← ¬is_prime(n) //toggle state
for n ≤ limit, n ← 3x²+y² where x ∈ {1,3,...} and y ∈ {2,4,...} // only odd x's
    if n mod 60 ∈ {7,19,31,43}:                                 // and even y's
        is_prime(n) ← ¬is_prime(n) //toggle state
for n ≤ limit, n ← 3x²-y² where x ∈ {2,3,...} and y ∈ {x-1,x-3,...,1} //all even/odd
    if n mod 60 ∈ {11,23,47,59}:                                   // odd/even combos
        is_prime(n) ← ¬is_prime(n) //toggle state

// Eliminate composites by sieving, only for those occurrences on the wheel
for n² ≤ limit where n ← 60 × w + x where w ∈ {0..}, x in s:
    if is_prime(n):
        // n is prime, omit multiples of its square; this is
        // sufficient because composites which managed to get
        // on the list must be prime square-free
        while c ≤ limit where c ← n² × m where
                      m ∈ {1,7,11,13,17,19,23,29, 31,37,41,43,47,49,53,59,...}:
            is_prime(c) ← false

output 2, 3, 5
for n ≤ limit where n ← 60 × w + x where w ∈ {0..}, x in s:
    if is_prime(n): output n

This pseudocode is written for clarity. Although some redundant computations have been eliminated by controlling the odd/even x/y combinations, it still wastes almost half of its quadratic computations on non-productive loops that don't pass the modulo tests such that it will not be faster than an equivalent wheel factorized (2/3/5) sieve of Eratosthenes. To improve its efficiency, a method must be devised to minimize or eliminate these non-productive computations.

Explanation[edit]

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[edit]

It can be computed[1] that the above series of three quadratic equation operations each have a number of operations that is a constant ratio of the range as the range goes to infinity; as well the prime square free culling operations can be described by the prime zeta function(2) with constant offsets and factors so it is also a constant factor of the range as the range goes to infinity. Therefore, the algorithm described above can compute primes up to N using O(N) operations with only O(N) bits of memory.

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(N1/2/log N) bits of memory plus a minimal page buffer. This is slightly better performance with the same memory requirement as the page segmented sieve of Eratosthenes which uses O(N log log N) operations and the same O(N1/2/log N) bits of memory[2] plus a minimal page buffer.

A special modified "enumerating lattice points" variation which is not the above version of the Sieve of Atkin can theoretically compute primes up to N using O(N/log log N) operations with N1/2 + o(1) bits of memory[1] but this variation is rarely if ever implemented, including by the authors. That is a little better in performance at a very high cost in memory as compared to both the ordinary page segmented version and to an equivalent but rarely if ever implemented version of the sieve of Eratosthenes which uses O(N) operations and O(N1/2(log log N)/log N) bits of memory.[3][4][5]

See also[edit]

References[edit]

  1. ^ a b c d e f g h i A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030.[1]
  2. ^ Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), pp. 17–35.
  3. ^ Paul Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981), 18–23. MR 82c:10011
  4. ^ Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. MR 84g:10015
  5. ^ Paul Pritchard, Fast compact prime number sieves (among others), Journal of Algorithms 4 (1983), 332–344. MR 85h:11080

External links[edit]