# Prime Number Sieving--A Systematic Review with Performance Analysis
## 3 Outcomes and Discussion
### Classic Sieve Algorithms
#### 3.2.2 From linear to sub-linear
SoP is very clever, but the complex data management overhead cancels out the gain in complexity; Bengelloun has very bad locality and uses divisions when it encounters composites, and this lowers the performance for big numbers, when primes become more and more scarce; Gale/Pratt was quite optimized from its inception, requires fewer operations to manage its data structure, and remains a good performer in its class of SoE-derived linear sieves, where only static wheels can save the day; Atkin is the best performer for large values, but still worse than 357. ### Parallel

The first step towards parallelization was made by [PERSON] in 1969 through 357's incremental mechanism, mentioned in Section 3.2.1--its goal was to save memory, but it is \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{\(N\)} & \multirow{2}{*}{\(\pi(N)\)} & \multicolumn{8}{c}{**Algorithms**} \\ \cline{3-10}  & & **[PERSON]** & **Gale/Pratt** & **[PERSON]/Misra** & **[PERSON]** & **[PERSON]** & **[PERSON]** & **W8 SoE** & **357** \\ \hline \(10^{5}\) & 9592 & 1 & 1 & 1 & 1 & 1 & 1 & 24 & - \\ \hline \(10^{6}\) & 78,498 & 8 & 4 & 9 & 4 & 9 & 4 & 26 & 2 \\ \hline \(10^{7}\) & 664,579 & 189 & 35 & 207 & 107 & 110 & 43 & 32 & 19 \\ \hline \(10^{8}\) & 5,761,455 & 1768 & 391 & 2204 & 1230 & 1336 & 796 & 167 & 174 \\ \hline \(10^{9}\) & 50,847,534 & 22,351 & 9615 & 24,143 & 15,738 & 13,761 & 9035 & 1771 & 1707 \\ \hline \(10^{10}\) & 455,052,511 & - & - & - & - & - & 125,367 & 22,968 & 18,415 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Timings (ms) for linear and sub-linear algorithms. also straightforward to segment the data, establish some boundary conditions, and then process each segment separately. One should also acknowledge the paper of [PERSON] from 1977 [39], which seems to be the first time that data segmentation is formally explained and detailed in relationship with prime generation. The authors provide appropriate boundary conditions for each data segment and formalized the technique: see Algorithm 13. 1. Generation of primes up to \(x=x_{0}+2k\Delta\) in two steps: (a) basic generation up to \(x_{0}\); (b) \(k\) iterations on a segment of length \(\Delta\) (_as only odd values will be represented in \(\Delta\)_)
2. Strike out multiples of each \(p_{i}\) in the set of _root primes_ inside \(\Delta\) from the start point \(y=mod_{p_{i}}(p_{i}-mod_{p_{i}}[(x_{0}-p_{i})/2])+1\) (boundary condition)
3. For each \(j\) left intact in \(\Delta\), \(p=x_{0}+2(j-1)\) is prime (_for 1-based indexes_)
4. The next iteration starts from \(x_{0}=x_{0}+2\Delta\) (_as odd numbers are skipped in \(\Delta\)_)

Unfortunately, parallel processing was not yet very popular--like [PERSON], the [PERSON]/[PERSON] paper does not address parallelization and their goal was to optimize memory footprint in an iterative approach, similar to [PERSON], but without the need to keep track of multiples between segments. This idea was again \"optimized\" for performance, creating something very similar to 357. It is not clear if they were aware of 357, as their Bibliography has only one entry ([PERSON]'s _Art of Programming_ vol.II), so probably their work was independent of [PERSON]'s. Where [PERSON] created an incremental algorithm but did not made the next step to segmentation, Bays/Hudson created the foundation of a segmented algorithm but reverted it back to an incremental one--nevertheless, it was a little early for the parallelization potential of these ideas to emerge. However, the idea of segmenting data was not new: it was mentioned, for example, as early as 1973 by [PERSON] [40] for a practical application of prime number sieving, being used to generate primes up to \(2.6\times 10^{12}\) to study the gaps between successive primes. It is notable that the article also mentioned the usage of a bit representation for each number, instead of the didactic byte, as suggested by [PERSON], but earlier than the practical example of Gale/Pratt.