Lecture
Sieve of Atkin — an algorithm for finding all prime numbers up to a given integer N. The algorithm was created by A. O. L. Atkin and D. J. Bernstein . The asymptotic running time claimed by the authors matches the speed of the best previously known sieving algorithms, but compared to them the Sieve of Atkin requires less memory.
The main idea of the algorithm consists in using irreducible quadratic forms (representing numbers as ax2 + by2). Previous algorithms were mostly various modifications of the Sieve of Eratosthenes, which used a representation of numbers as reduced forms (typically as a product xy).
In simplified form, the algorithm can be presented as follows:
To reduce memory requirements, «sieving» is carried out in portions (segments, blocks), whose size is approximately 
.
To speed up the work, the algorithm ignores all numbers that are multiples of one of several of the first primes (2, 3, 5, 7, …). This is done by using standard data structures and processing algorithms proposed earlier by Paul Pritchard (English: Paul Pritchard) . They are known as English: wheel sieving. The number of first primes chosen depends on the given number N. Theoretically it is suggested to take the first primes up to approximately 
. This makes it possible to improve the asymptotic estimate of the algorithm's speed by a factor of 
. This, however, requires additional memory, which as N grows is bounded as 
. The increase in memory requirements is estimated as 
.
The version presented on one of the authors' website , is optimized for finding all prime numbers up to one billion (
); it excludes from the calculations numbers divisible by 2, 3, 5 and 7 (2 × 3 × 5 × 7 = 210).
According to the authors' estimate , the algorithm has asymptotic complexity 
and requires 
bits of memory. Previously, algorithms were known that were equally asymptotically fast but required substantially more memory . In theory, this algorithm combines maximum speed with the lowest memory requirements. The implementation of the algorithm made by one of the authors shows a fairly high practical speed .
The algorithm uses two kinds of optimization that substantially increase its efficiency (compared to the simplified version).
Below is an implementation of the simplified version in the C programming language, illustrating the main idea of the algorithm — the use of quadratic forms:
Comments