# Prime Number Sieving--A Systematic Review with Performance Analysis
## 3 Outcomes and Discussion
### Classic Sieve Algorithms
#### 3.2.2 From linear to sub-linear
* Slow sieves--performance degrades drastically with \(N\) (like trial-division or SoS). * Space complexity of the sieve:
* Compact sieves--complexity is \(\mathbf{O}(\sqrt{N})\) or better (incremental or segmented sieves). * Normal sieves--complexity is around \(\mathbf{O}(N)\) (like simple SoE or the linear ones). * Huge sieves--space requirements increase drastically with \(N\) (hopping sieve). * Operations implied by the optimized algorithm:
* Additive sieves--only additions, subtractions and simple bit operations in the inner loop (like SoP). * Regular sieves--some multiplications allowed in the inner loop (like Mairson, Singleton, etc.). * Complex sieves--all operations: division, modulo etc. (trial division, basic SoA and Bengelloun, etc.). * The end condition of the sieve:
* Perpetual sieves--given appropriate resources, it can run forever without resetting the calculus (357, Bengelloun). * Caped sieves--can compute primes up a certain limit; changing the limit implies complex re-adjustments (almost all others). * The availability of the results:
* Incremental sieves--iterations are relatively short and each iteration produces the next one or more prime numbers based on the results of the previous iteration (Chartres, Singleton, Bengelloun). * Solid sieves--the whole set of primes is produced in one or a relatively small number of big, unrelated batches (almost all others). * The treatment of the set of candidates:
Integral sieves--the algorithm works on the whole set at once, or on a small number of very big batches in a certain order (basically all the sieves are born and initially presented as solid sieves; many are now segmented, but for some sieves like Mairson no segmentation technique was discovered). * Segmented sieves--the algorithm works on a relatively large number of small, unrelated subsets of the whole dataset, in an arbitrary order (segmented algorithms are usually an adaptation of solid sieves--most algorithms are not initially segmented, although some, like SoA, may be presented from the start in their segmented version). Of course, the goal would be to obtain a strongly sub-linear, compact, additive, perpetual, incremental and segmented sieve. There are also other criteria that should be noted:

How the candidates are produced: start from the full set of numbers in the interval of interest (practically all sieves apart SoP) or generate, from the beginning, a drastically reduced set of candidates that may considerably limit the volume of work (like SoP and static-wheel-based SoE);

The goal is to simply count the primes, or to effectively generate the prime numbers--if the latter, consider whether they will be produced in order;

The criteria used to eliminate composites: whether they are based on multiples of root primes (like SoE and most of the others), or on more complex polynomial expressions (like SoS or SoA). ### Perspectives

A contiguous list of primes up to \(2^{64}\) could further advance prime number theory, providing valuable insights into prime distribution and patterns, and would allow for primes to be generated in any interval up to \(2^{128}\) (reaching the \(2^{128}\) barrier will provide us with access to \(2^{256}\) ranges, etc.). However, the sad reality is that we can now pragmatically and routinely produce very large discrete prime numbers, but we are not able to systematically generate in reasonable time all the prime numbers that our 64 bit processors can manage natively. Given the latest advances in both CPU and GPU power, perhaps it is time to re-ignite the ambition to refine existing, or create new, algorithms for the systematic generation of prime numbers in continuous sequence.