# Prime Number Sieving--A Systematic Review with Performance Analysis
## 3 Outcomes and Discussion
### Classic Sieve Algorithms
#### 3.2.2 From linear to sub-linear
Then, after obtaining, \(p_{next}=\) the immediate next prime greater than \(p\), the number \(n_{next}=p_{next}\times q\), is struck out by inscribing \(p_{next}\) in the \(lpf\) vector at position \(n_{next}\). See Algorithm 11 and accompanying code for details. ```
1 uint64_tBen(constuint64_tNmax,uint64_t*p,uint64_t*lpf)
2{
3 lpf[1]=lpf[2]=0; uint64_tsz_lpf=2,sz_p=0; for(uint64_tn=2;n<=Nmax;n++)
4{
5 if(lpf[n]==0){p[++sz_p]=n;lpf[n]=sz_p;} else
6{
7 uint64_tq=n/p[lpf[n]]; if(lpf[n]<lpf[q]){uint64_t=lpf[n]+1;lpf[q*p[r]]=r;}
8} lpf[++sz_lpf]=0;lpf[++sz_lpf]=1;
9} returns sz_p;
```
**Algorithm 11** Bengelloun Continuous Incremental Primal Sieve

This incremental sieve was improved by [PERSON] in 1994 [34], and transformed in a incremental additive and sub-linear sieve using wheels. In 1987, [PERSON] performed an interesting analysis [35] of the linear algorithms found so far and synthesized them all by generalizing families of variations in the generic process of eliminating composites \(c\), with two general expressions:

* based on **least prime factor**: \(c=p\times f\), where \(p=\)lpf\((c)\) (from this family, [PERSON], [PERSON]/[PERSON], [PERSON], and [PERSON] can be derived, but also two new siblings--called simply **3.2** and **3.3**--with the same linear character);
* based on **greatest prime factor**: \(c=p\times f\), where \(p=\)gpf\((c)\) (from this family, [PERSON] and [PERSON] can be derived, but also two new siblings--called **4.3** and **4.4**--with the same linear character). Finally, in 2003, we received a new, completely different type of sieve: a quadratic sieve--**Sieve of Atkin (SoA) [36]--which has a theoretical complexity equal to SoP. (_An interesting fact is that SoA was cited by [PERSON] [37] in 2000, some years before the official publication; [PERSON] referenced a paper of [PERSON]/[PERSON] from 1999, and the URL cited by [PERSON] for that paper--_[[http://polyox.com/~djb/papers/primesieves.dvi--accessed](http://polyox.com/~djb/papers/primesieves.dvi--accessed)]([http://polyox.com/~djb/papers/primesieves.dvi--accessed](http://polyox.com/~djb/papers/primesieves.dvi--accessed)) on 10 April 2024. )SoA is based on the mathematical properties of some quadratic forms, thus being more related to SoS than SoE. It is quite promising, but relatively boring from the algorithmic perspective in its basic implementation. It capitalizes on the fact that all the numbers \(p=12k+d\) that (a) have an odd number of positive solutions at these equations:

* \(p=4x^{2}+y^{2}\), where \(d=1\) or \(5\), \(x\) and \(y>0\)
* \(p=3x^{2}+y^{2}\), where \(d=7\), \(x\) and \(y>0\)
* \(p=3x^{2}-y^{2}\), where \(d=11\), \(x>y>0\)

and (b) are squarefree (not a multiple of a square) are primes (in the original paper, one can find the justification for these properties, based on some more general \(p=60k+d\) considerations). Frequent modulos and multiplications impair the performance, but the results are quite decent. See Algorithm 12 and function _Atkin_ in the accompanying code for further details). ```
1. Initialize a sieve vector
2. For all eligible pairs (x,y) mark the values of the quadratic forms in the vector
3. Remove from the vector all values corresponding to: (a) even number of solutions
4. (b) multiples of squares
5. Count or otherwise use the primes indicated by the vector
```

**Algorithm 12** Sieve of Atkin

The original technique is somewhat improved by [PERSON] in [37], where the sieve is further segmented. Also, in [38], one can find some other interesting theoretical considerations regarding SoA. Table 3 presents single-threaded timings for all these algorithms, including 357 as a baseline:

In conclusion, all the sub-linear sieves were better than a basic SoE, but they still were not close to the incremental 357 that, on modern CPUs, will use the cache for important performance gains.