Sieve of Atkin — The Theoretical Optimization of Prime Number Generation
Sieve of Atkin is an algorithm developed to optimize the generation of prime numbers. This algorithm was created in 2003, after A.O.L. Atkin and D.J. Bernstein published their paper on how to calculate primes using binary quadratic forms. Sieve of Atkin was intended to optimize the time complexity of its predecessor: Sieve of Eratosthenes.
The Algorithm and Implementation
As the name suggests, the algorithm acts as a sieve and filters out the composite numbers in a list based off of the mathematical rules and equations derived in Atkin and Bernstein’s paper. This algorithm takes in a parameter that defines the limit at which we want to stop looking for prime numbers. This means if the limit was 100, we would search for prime numbers from 1–100. We can call this parameter limit. This particular implementation prints out the list of primes rather than saving it to an array separate from the composite numbers.
The algorithm begins by comparing limit to the special case prime numbers, 2 and 3. If limit is less than either of these two numbers then we can stop here. We then initialize the boolean sieve array and set all its values as false. This array will keep track of which elements are prime and which are not. All elements are set as false until they are found to be prime.
Now that we have our list of numbers, we can begin determining which ones are prime. We do this by evaluating elements against a set of three conditions that are proved in Atkin’s paper.
Condition One
The first condition has two parts. The first part is that int n, or the solution to the equation 4x² + y² based on x and y values which I will discuss later, is within the bounds of limit. The second part is that n has a modulo-12 remainder of 1 or 5. This means that when divided by 12, the n has a remainder of 1 or 5. If both of these are true, then we can set the value at the nth index of sieve true, meaning it is a prime number.
Condition Two
The second condition also has two parts. The first is, again, that int n is within the bounds of limit, except this time the equation is equal to 3x² + y². The second part is that n has a modulo-12 remainder of 7. If both of these are true, then we can mark the nth index of sieve as prime.
Condition Three
This condition is very similar to the previous two, except n is now equal to 3x²-y². If n is within the bounds of limit and has a modulo-12 remainder of 11, then we can mark the nth index of sieve as prime.
Calculation of X and Y
The three conditions above all included the calculation of int n. This integer depends on different equations for each condition which all contain the variables x and y. These variables are defined by nesting all three of these conditions in a nested for loop which iterates through all possible values of x and y. This ensures that all values of x and y, within the bounds, are explored.
Filter Out Non-Primes
Because of the nature of the algorithm, some composite numbers were able to slip through and be classified as prime. To fix this we can implement the following code. We can loop through all numbers in sieve starting at r = 5 and if r is prime then the value at the index of r² and its multiples are set back to false.
Printing Out the Primes
Now our logic is finished and we have a complete list of primes between 1 and limit. It’s time to print out the result. We already printed out 2 and 3 at the beginning, so we can loop through sieve and print out all true elements beginning at element 5.
Sieve of Atkin Logical Walkthrough
A quick walkthrough of the logic might help to visualize how the algorithm executes. We will begin with this number line below, which represents a parameter of limit = 25 being passed in to our algorithm. The green dot represents a true value in the boolean sieve array, also known as prime. The red dot represents the opposite, and the black dot represents a prime number that has been outputted to the screen.
According to the code above, our first step would be to output 2 and 3. Then we change all values in sieve to false. Since 2 and 3 are special case prime numbers, we don’t change their boolean value in sieve to true. So they will continue to be depicted as false in our array below.
Using the conditions provided by Atkin’s paper, and by plugging in all x and y values that keep the equation within our limit of 25, we get these values for n. In the code, this is where we go through the nested for loops for each x and y value and use it in the equation for each condition.
We still have to compare these outputs for n to the remainders for each condition. The green values indicate that the condition was met and the sieve array should be updated. The red values indicate that the equation is not valid and therefore the condition was not met. These values are confirmed to not be prime.
Now we have marked all the prime numbers in our array, however there may be some values marked as prime which are composite.
Just by looking at these values we can tell which ones should not be considered prime, but let’s use the algorithm to change the composite value marked as prime. The algorithm tells us to change any prime number who’s square or square multiple is considered a prime. The only value in this array that has a square which is also in this array is 5. This means we should change 25’s boolean value to false. Now we have completed our array of prime numbers and can began outputting the numbers to the screen.
The prime numbers between 1 and 25 should be: 2, 3, 5, 7, 11, 13, 17, 19, 23. Congratulations! You have successfully walked through the Sieve of Atkin algorithm.
Time Complexity
With this implementation of Sieve of Atkin, the time complexity is O(N), or linear. The number of operations required in the quadratic equation increase linearly as N, the limit that is passed in as a parameter , increases.
This nested for loop, which is used to pick out the composite numbers categorized as primes, slightly resembles an O(N²) time complexity. This is due to the structure of the for loops and the double iteration through the sieve array. However, it is also O(N) because on the inner for loop int i is such a large number and is limited by limit so you are only iterating over a few values in sieve.
It’s predecessor, Sieve of Eratosthenes has a time complexity of O(N log(log N)), which is unfortunately better than Sieve of Atkin. Sieve of Eratosthenes dominates at lower N limits, as seen in the times shown below in microseconds.
However, using a different implementation of Sieve of Atkin with enumerating lattice points can result in a theoretical time complexity of O(N / log log N). This is where Sieve of Atkin takes the prize. As N gets larger, Sieve of Atkin will begin to have a more efficient time complexity than Sieve of Eratosthenes. By graphing these two time complexities we can see exactly where Sieve of Atkin becomes more efficient. Sieve of Atkin is graphed in blue and Sieve of Eratosthenes is in red.
This graph shows that at ten billion prime digits, Sieve of Atkin will become more efficient. There is a reason this is the better “theoretical” time complexity, and that’s because by the time you reach this point you would likely run out of memory, therefore Sieve of Atkin offers almost no real benefit other than its uniqueness.
Links To Code
My GitHub repository with code demonstrating both Sieve of Atkin and Sieve of Eratosthenes.
Further Reading/References
Atkin and Bernstein Paper
Sieve of Atkin History and Overview
Sieve of Atkin Implementation and Pseudocode
Sieve of Atkin Implementation and Time Complexity
Sieve of Eratosthenes Implementation and Pseudocode
