In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, the sieve of Atkin does some preliminary work and then marks off multiples of squares of primes, thus achieving a better theoretical asymptotic complexity. It was created in 2003 by A. O. L. Atkin and Daniel J. Bernstein.
Algorithm
In the algorithm:
- All remainders are modulo-sixty remainders (divide the number by 60 and return the remainder).
- All numbers, including and , are positive integers.
- Flipping an entry in the sieve list means to change the marking (prime or nonprime) to the opposite marking.
- This results in numbers with an odd number of solutions to the corresponding equation being potentially prime (prime if they are also square free), and numbers with an even number of solutions being composite.
The algorithm:
- 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 non prime (composite).
- For each entry number in the sieve list, with modulo-sixty remainder :
- If is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to . The number of flipping operations as a ratio to the sieving range for this step approaches This makes use of a boolean array to mark integers as being prime, or not. <syntaxhighlight lang="java" line="1">public static List<int> sieveOfAtkin(int limit) {
boolean[] arr = new boolean[limit + 1]; // initialised by false on default
// mark 2 and 3 as prime
if (limit > 2) arr[2] = true;
if (limit > 3) arr[3] = true;
// check for all three conditions
for (int x = 1; x * x <= limit; x++) {
for (int y = 1; y * y <= limit; y++) {
// condition 1
int n = (4 * x * x) + (y * y);
if (n <= limit && (n % 12 == 1 || n % 12 == 5))
arr[n] = ! arr[n];
// condition 2
n = (3 * x * x) + (y * y);
if (n <= limit && n % 12 == 7)
arr[n] = ! arr[n];
// condition 3
n = (3 * x * x) - (y * y);
if (x > y && n <= limit && n % 12 == 11)
arr[n] = ! arr[n];
}
}
// Mark all multiples
// of squares as non-prime
for (int i = 5; i * i <= limit; i++) {
if (arr[i] == false) continue;
for (int j = i * i; j <= limit; j += i * i)
arr[j] = false;
}
// store all prime numbers
List<int> primes = new List<int>();
for (int i = 2; i <= limit; i++) {
if (arr[i] == true) {
primes.Add(i);
}
}
return primes;
}</syntaxhighlight>
Note that while the above implementation is true to the intent of the Atkin algorithm, it is not an example showing the true computational complexity of the algorithm due to many redundant operations above as described by the algorithm - note that `25 + 60k` and `55 + 60k` where `k` is all non-negative integers fall through the modulo tests for a constant factor increase in the number of operations although these errors are compensated for by running the squares-free operation from multiples of 5 rather than the 7 as would be used by the true algorithm for an increase above a constant factor. Worse, the `x` and `y` values are allowed to range up to the limit value rather than limiting them to values less than the limit by large factors resulting a huge increase in computational complexity for redundant operations that do not contribute to the result. For these reasons, the above implementation does not show the `O(n)` asymptotic computational complexity of which the algorithm is capable and is not true to the pseudo code above.
Explanation
The algorithm completely ignores any numbers with remainder modulo 60 that is divisible by 2, 3, or 5, since numbers with a modulo-60 remainder divisible by one of these three primes are themselves divisible by that prime.
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 is odd and the number is squarefree (theorem 6.1 of plus a minimal page buffer. However, such a sieve does not outperform a sieve of Eratosthenes with maximum practical wheel factorization (a combination of a 2/3/5/7 sieving wheel and pre-culling composites in the segment page buffers using a 2/3/5/7/11/13/17/19 pattern), which, despite having slightly more operations than the Sieve of Atkin for very large but practical ranges, has a constant factor of less complexity per operation by about three times in comparing the per-operation time between the algorithms implemented by Bernstein in CPU clock cycles per operation. The main problem with the page-segmented sieve of Atkin is the difficulty in implementing the prime-square-free culling sequences due to the span between culls rapidly growing far beyond the page buffer span; the time expended for this operation in Bernstein's implementation rapidly grows to many times the time expended in the actual quadratic equation calculations, meaning that the linear complexity of the part that would otherwise be quite negligible becomes a major consumer of execution time. Thus, even though an optimized implementation may again settle to a time complexity, this constant factor of increased time per operations means that the sieve of Atkin is slower.
A special modified "enumerating lattice points" variation of the sieve of Atkin can theoretically compute primes up to ' using operations with bits of memory,
Pritchard observed that for the wheel sieves, one can reduce memory consumption while preserving Big-O time complexity, but this generally comes at a cost in an increased constant factor for time per operation due to the extra complexity. Therefore, this special version is likely more of value as an intellectual exercise than a practical prime sieve with reduced real time expended for a given large practical sieving range.
See also
- Sieve of Eratosthenes
- Legendre sieve
- Sieve of Sundaram
- Sieve theory