# 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 updated but accurate version of this algorithm, translated into C++, can be found in the accompanying code (function _GalePratt_). Another version of SoE+ was published [24] by [PERSON]/Misra the following year, capitalizing on the work of [PERSON]. [PERSON]'s sieve was advertised as linear, but practice proved it to be much less efficient than 357. [PERSON]/Misra had a similar idea for sifting primes through candidates and strove to achieve linearity by proposing a streamlined technique to manage the data. The sieve is also reminiscent of that of Gale/Pratt, processing composites formed by powers of the current \(p\). While [PERSON] iterates for each first number \(p\) left in the list and strikes out the products between \(p\) and every number left in the list at that point, [PERSON]/Misra iterate for each first number \(p\) left in the list and strike out the products between all powers of \(p\) and the next numbers in the list. Figure 2 depicts the steps of [PERSON] vs. Gries/Misra primes combing algorithms. Each column contains all the numbers remaining in that step, with those marked for deletion highlighted blue. Both techniques strike out each composite exactly once, hence the basic linear character of the algorithms, but [PERSON] may strike out numbers that are to be used later in the same iteration, leading to more complications in data management

to preserve the numbers that are marked until the end of the current cycle. Moreover, Gries/Misra eliminate the need for the third vector, lowering the memory requirements: see Algorithm 9 (all the details are provided in the accompanying code). ```
1 uint64_tGriesMisra(constuint64_tNmax,uint64_trlink[],uint64_tllink[])
2{...}//initializationuint64_tnsqrt=(uint64_t)ceil(sqrt(Nmax));for(uint64_tp=2;p<=nsqrt;p=rlink[p]){uint64_tq=p;for(uint64_tpq=p*q;pq<=Nmax;pq=p*q){for(uint64_tx=pq;x<=Nmax;x*=p)crossoff(x);q=rlink[q];}
3}
4{...}//counting
```
**Algorithm 9** Gries/Misra linear sieve

The same article [24] includes a discussion regarding the underlying data structure, showing how one can substitute a pointers vector with a vector of booleans to achieve further memory savings. Due to the great similarity between the two, these optimizations can also be applied to Mairson. In theory, Gries/Misra should perform marginally better, because the same number of composites are removed and data management is simpler--in practice, because Gries/Misra has much worse locality (fewer composites are identified per cycle, so a lot of cache is trashed), Mairson performs better. The next big thing in prime sieving appeared in 1981, in a paper from [PERSON], introducing what is probably the most beautiful prime sieving algorithm: **Wheel of Pritchard** (SoP) [26]. The algorithm was further clarified by the author in [27]. SoP technique is derived from [PERSON]'s, except it does not parse the whole set of candidates for each \(p\) to eliminate multiples, but instead tries to iteratively and incrementally generate the smallest possible set of candidates to work on. In order to understand the algorithm, we need to recap some basic mathematical ideas:

* The product of the first \(n\) primes is called **Primorial**:

\[P(n)=\prod_{i=1}^{n}p_{i}\quad(\leftarrow\quad p_{1}=2,p_{2}=3,...\quad p_{i} \text{ is prime}) \tag{9}\]
* If \(\delta\) is coprime with any \(p_{i}\), then \(P(n)+\delta\) is also coprime with any \(p_{i}\). Let us construct a set (wheel) \(S_{n}\) with all \(\delta<P(n)\), where \(\delta\) is coprime with all primes \(p_{i}\) for \(i<n\). First, it is evident that any \(p_{i}\) is coprime with any other \(p_{j}\), so we can use these as values for \(\delta\). Thus, it is clear that any \(p=kP(n)+\delta\) will remain coprime with all \(p_{i}\). Extending this to all such \(p\) where \(p<P(n+1)\) and then removing all multiples of \(p_{n}\) will give us the new \(S_{n+1}\), hence the iterative algorithm used to generate primes. Unfortunately, \(P(n)\) increases very steeply with \(n\), so it is very hard to create a table representation of the algorithm progression.