Atkin sieve
The sieve of Atkin is a fast, modern algorithm for determining all prime numbers up to a predetermined limit. It is an optimized version of the ancient sieve of Eratosthenes : The Atkin sieve does some preliminary work and then crosses out all multiples of prime squares. It was developed by A. O. L. Atkin and Daniel J. Bernstein .
algorithm
- All residues are modulo -60 residues (the remainder after division by 60 is considered).
- All numbers, including x and y , are positive integers.
- In the following, inverting an entry in the sieve list means that its marking (prime or not prime) is changed to the opposite.
- Create a list of results filled with 2, 3 and 5.
- Create a sieve list with one entry for each positive integer; all entries in this list are initially marked as not prime.
- For each entry n in the sieve list do the following:
- If the entry contains a number with a remainder of 1, 13, 17, 29, 37, 41, 49, or 53, invert it for every possible solution to the equation: 4 x ² + y ² = n .
- If the entry contains a number with a remainder of 7, 19, 31, or 43, invert it for every possible solution to the equation: 3 x ² + y ² = n .
- If the entry contains a number with remainder 11, 23, 47, or 59, invert it for every possible solution to the equation: 3 x ² - y ² = n , where x > y .
- Start with the lowest number on the sieve list.
- Take the next number on the sieve list that is still marked as prime.
- Add the number to the list of results.
- Square the number and mark all multiples of that square as non-prime.
- Repeat steps 5 through 8.
Explanation
The algorithm ignores any numbers that are divisible by two, three, or five.
- All numbers with modulo 60 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 60 remainder 3, 9, 15, 21, 27, 33, 39, 45, 51 or 57 are divisible by three and not prime.
- All numbers with modulo 60 remainder 5, 25, 35 or 55 are divisible by 5 and not prime. These leftovers are all ignored.
- All numbers with modulo 60 remainder 1, 13, 17, 29, 37, 41, 49 or 53 have a modulo 4 remainder of 1. These numbers are prime if and only if the number of solutions for 4 x ² + y ² = n is odd and the number is free of squares .
- All numbers with modulo 60 remainder 7, 19, 31 or 43 have a modulo 6 remainder of 1. These numbers are prime if and only if the number of solutions for 3 x ² + y ² = n is odd and the number is square-free .
- All numbers with modulo 60 remainder 11, 23, 47 or 59 have a modulo 12 remainder of 11. These numbers are prime if and only if the number of solutions for 3 x ² - y ² = n is odd and the number is square-free .
- None of the potential prime numbers are divisible by 2, 3, or 5, so they cannot be divisible by their squares. Therefore, the square freedom is not checked at 2², 3², and 5².
complexity
Atkin's sieve has a run time complexity of and a memory footprint of bits.
For comparison: the sieve of Eratosthenes has a runtime complexity of and needs bits.
Here is the Landau symbol and the number of numbers to be examined.
literature
- AOL Atkin, DJ Bernstein, Prime sieves using binary quadratic forms (PDF; 185 kB), (1999).
- AOL Atkin, DJ Bernstein, Prime sieves using binary quadratic forms (PDF; 170 kB), Math. Comp. 73: 1023-1030 (2004).