# Prime Number Sieving--A Systematic Review with Performance Analysis
## 3 Outcomes and Discussion
### Classic Sieve Algorithms
#### 3.2.2 From linear to sub-linear
CUDASieve ([[https://github.com/curtsseizert/CUDASieve](https://github.com/curtsseizert/CUDASieve)]([https://github.com/curtsseizert/CUDASieve](https://github.com/curtsseizert/CUDASieve)), accessed on 10 April 2024)--a GPU accelerated C++/CUDA C fast sieve. Both implementations use the so-called _bucket list_ technique to store the root primes into lists of buckets: each list is associated with a segment, and a list contains only those primes that have multiples in that segment. The technique was devised by [PERSON] [49], and was used in his project for Goldbach conjecture verification that reached \(4\times 10^{18}\)[50; 51]. ### Other Sieve Variants

In 1965, [PERSON] [52] introduced an original idea: he theorized a one-dimensional iterative array of finite-state sequential machines that could represent a set of prime numbers. [PERSON] provided a solution to the problem, but also states that his solution is less efficient than SoE. Unfortunately, although the usage of such _cellular automata_ for discrete prime number generation was explored in some papers, there was very little follow-up on this approach in order to achieve better efficiency for practical systematic prime generation. Some occasional references to this idea ([53; 54; 55]) appear to have mainly didactic purposes. There were some tentative attempts to implement sieving using the _functional programming_ paradigm [56; 57; 58] but these, too, seem more didactic in nature and exceed our scope and ambition. Another category of sieves are those using some punctual primality tests, like AKS test in [59], which simply apply the test to all the numbers in the desired range. These include also examples like [PERSON] [60], which uses the pseudosquares primality test, or [PERSON] [61], which uses the Rabin-Miller test--this approach normally achieves a horrendous performance, as these tests are extremely complex. There were tentative attempts to compute the \(n\)th prime number, usually derived from generic formulas similar to [PERSON] [62] as in [63; 64]: again, these formulas are extremely complex and lead to horrific performance. There are some alternatives that may merit more study: [PERSON]'s \"hopping sieve\" ([65]), also detailed in [66]; the NPNG/FTF scheme from [67]; algorithms based on the divisibility of two consecutive numbers, like in [68; 69]; techniques using Scheduling by Multiple Edge Reversal (SMER), like in [43; 44]. The idea based on Diophantine approximation and [PERSON]'s work on the Dirichlet divisor problem [70], from [PERSON] (the mathematician who proved [PERSON]'s weak conjecture ) is also interesting. ## 4 Conclusions

The first sieving algorithm was published in 1961 by [PERSON], followed by contributions from [PERSON] and [PERSON]. [PERSON]. [PERSON], [PERSON], and [PERSON]/[PERSON] worked oh linear sieves in the late 1970s, while [PERSON]/[PERSON] introduced the segmentation technique for SoE. [PERSON] created his sub-linear sieve in the 1980s, and [PERSON] published several meaningful articles in the 1990s. The last major contribution was made in 2003 by [PERSON]/[PERSON], with Sieve of Atkin, which was born segmented and remains the practical sieve with the lowest theoretical complexity. No relevant algorithmic advances were identified after this, besides the optimization of parallelized SoE. Most of the papers published since 2000 deal with the parallelization of SoE (and occasionally SoP), but these papers are quite narrow and mostly didactic in purpose--as if everybody agrees that there is nothing more to be said on this topic. Authors usually just apply newer hardware and software techniques to the old SoE, and the main focus is usually on the generic techniques and not the actual sieving algorithm. ### A sieve Taxonomy

A sieve classification may consider the following set of characteristics:

* Arithmetic complexity of the sieve:
* Sub-linear sieves--complexity is better than \(\mathbf{O}(N)\) (like SoP or SoA). * Linear sieves--complexity is arround \(\mathbf{O}(N)\) (examples provided in Section 3.2.1).