# Prime Number Sieving--A Systematic Review with Performance Analysis
## 3 Outcomes and Discussion
### Classic Sieve Algorithms
#### 3.2.2 From linear to sub-linear
An important work regarding segmentation was published by [PERSON] in 1983 [28], where he presents a useful, linear technique to segment a sieve based on static wheels--nevertheless, again, the goal was to minimize memory requirements and not parallelization. The results were refined by [PERSON] in 1990 [29]. An article from 1987 by [PERSON] [41] talks about multiprocessing SoE, but employs a very naive version of parallelization: it does not segment the data, but launches one process for each root prime to strike out composites--instead of data parallelism, it uses some form of task parallelism, which is not really appropriate here, and requires a lot of synchronization. The goal of this exercise was to test a new hardware (Flex/32) and not to generate primes per se--still, we have to appreciate this as the first recorded attempt to parallelize a prime generator sieve. Other works of that period are referenced in some articles and may have some interesting content, but we cannot find them anymore. These include _Parallel sieve methods for generating prime numbers_ (1980) by [PERSON], [PERSON], [PERSON], _Parallel speedup of sequential prime number sieves_ (1981) by [PERSON], or _Massively Parallel Mathematical Sieves_ by [PERSON]. In 1994, [PERSON] [42] tried to address the problem of latency and provided two solutions--one for low and another for high communication latency. The first solution is based on **Algorithm 3.3** from [PERSON] [35] improved using a static wheel, as in [28]--this is not a very useful idea in practice, as each worker will have to parse the whole \([2..N]\) data segment and then overlap all the results, like in [41]. The second version is more realistic, with a true data segmentation--the final step is to concatenate all data. This result is a formula that can compute the boundary conditions for each segment in the case of a static wheel. In 2005 we found some attempts to parallelize SoP by [PERSON] [43; 44], while in 2007 we found a coarse attempt to balance the load of a basic SoE in [45]. In the same year, [PERSON] et al. [46] used MPI to parallelize a sieve, but the \"sieve\" used in this work was a brute force (trial-division) algorithm. As in most papers regarding sieve parallelization, the main area of interest was not the sieve itself, but some practical or theoretical aspects linked to parallel computing, and the sieve was only used to demonstrate the problem and provide a possible solution. Similar, in 2010, there was an attempt by [PERSON] et al. [47] to apply statistical DOE to SoE. Again, the article is more preoccupied with the methodology of efficiently deploying large-scale numerical applications on grid platforms than with SoE specifically. When RAM is simply not enough, using another type of data repository can be quite taxing on performance--one can find some interesting insights regarding the I/O complexity of sieves in [48]. In addition to official studies, there was some activity in small communities of enthusiasts on the internet. There are notable active sieving projects that are currently looking for very large primes, like PrimeGrid ([[https://www.primegrid.com/](https://www.primegrid.com/)]([https://www.primegrid.com/](https://www.primegrid.com/)), accessed on 10 April 2024) or GIMPS ([[https://www.mersenne.org/](https://www.mersenne.org/)]([https://www.mersenne.org/](https://www.mersenne.org/)), accessed on 10 April 2024), but these efforts are not really about advancing systematic prime generation, which is the focus of this study. The most interesting initiatives related to our domain are two very compelling projects hosted on GitHub, both implementing the segmented sieve of Eratosthenes:

1. primesieve ([[https://github.com/kimwalisch/primesieve](https://github.com/kimwalisch/primesieve)]([https://github.com/kimwalisch/primesieve](https://github.com/kimwalisch/primesieve)), accessed on 10 April 2024)--a parallel CPU cache intensive generator;
2.