# Prime Number Sieving--A Systematic Review with Performance Analysis
## 3 Outcomes and Discussion
### Classic Sieve Algorithms
#### 3.2.2 From linear to sub-linear  
The first linear algorithms appeared in the late 1970s, published by [PERSON] [22], [PERSON] [23] and [PERSON] [24]. [PERSON]'s 1977 article introduces an algorithm using an intricate data structure based on a triple vector representation of a double linked list and strives to compute each composite only once. The algorithm is very similar to SoE+, as you can see in Figure 2. It is not clear if [PERSON] knew about [PERSON]'s sieve--in any case, this is not mentioned in the paper. [PERSON] claimed a sub-linear time complexity for his algorithm; however, in practice, the memory complexity is very high and the performance is not optimal, as shown in Table 3. The basic operations used to identify the composites may have \(\mathbf{O}(N)\); but when these operations are considered together with all the overhead necessary to maintain the \begin{table}
\begin{tabular}{c r r r r r} \hline \hline \multirow{2}{*}{**N**} & \multirow{2}{*}{**\(\boldsymbol{\pi}\)(N)**} & \multicolumn{4}{c}{**Algorithms**} \\ \cline{3-6}  & & **Trial-Division (35)** & **Basic SoE** & **Generator 2 / 356** & **357** \\ \hline \(10^{5}\) & 9592 & 5 & 1 & 1 & - \\ \hline \(10^{6}\) & 78,498 & 80 & 2 & 12 & 2 \\ \hline \(10^{7}\) & 664,579 & 1580 & 16 & 132 & 19 \\ \hline \(10^{8}\) & 5,761,455 & 34,560 & 431 & 1566 & 174 \\ \hline \(10^{9}\) & 50,847,534 & - & 4640 & 18,339 & 1707 \\ \hline \(10^{10}\) & 455,52,511 & - & 57,752 & - & 18,415 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Timings (ms) for the very early algorithms. relatively complex data structure, the things get rapidly out of control--see Algorithm 7 (function _Mairson_ in the accompanying code offers an accurate rendition of the algorithm). ```
1 uint64_tMairson(uint64_tNmax,tpUnsignedDELETE[],
2
3
4 totUnsignedrlink[],tpUnsignedlink[])
5
6 autocrossoff=[&](tpUnsignedi)
7{rlink[llink[i]]=rlink[i];llink[rlink[i]]=llink[i];};
8[...]//initialization
9 tUnsignednsqrt=(tpUnsigned)floor(sqrt(Nmax));
10 for(tpUnsignedprime=2;prime<=nsqrt;prime=rlink[prime])
11 tUpUnsignedfactor=prime,pointer=0;
12 for(tpUnsignedk=prime*factor;k<=Nmax;k=prime*factor)
13{DELETE[+pointer]=k;factor=rlink[factor];}
14 for(tpUnsignedi=1;i<=pointer;i++)
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
29
29
29
29
29
29
29
29
29
29
29
29
299
29
299
299
299
299
2


```
1 uint64_tGalePratt(uint64_tNmax,uint8_tsv[]){
2[...]//initializations
4 for(i=3;i<=Nmax/2;i+=2) if(notPrime(i))
5 for(autoj:s)
7k=j;
8 while(k<Nmax)
9 if((k!=1)and(k!=i)and(k!=j))
10 MarkComposite(k);
11m=k*i;
12 if(m<Nmax)ts.push_back(k);
13k=m;
14s=ts;ts.resize(0);
15[...]//counting
```
**Algorithm 8** Gale and Pratt sieve

To optimize the memory footprint, [PERSON] [25] proposes to eliminate multiples in reverse order, thus avoiding the need for a third vector ([PERSON] later used this idea for his sieve). However, finding the start position (the position of the first value to eliminate) has a serious negative impact on the processing time, which we value the most. In the same year as [PERSON], [PERSON] published a paper [23] about MACLISP/CGOL, where he proposes, as an example, another linear sieve, credited to [PERSON] and [PERSON]. The logic behind this sieve is a little more convoluted--for each prime \(p\), it strikes out composites formed by the powers of \(p\) and all reasonable composites stricken out in the previous iteration(s). The substance of the algorithm is presented in Algorithm 8. ```
1 uint64_tGalePratt(uint64_tNmax,uint8_tsv[]){
2[...]//initializations
3 for(i=3;i<=Nmax/2;i+=2) if(notPrime(i))
4 for(autoj:s)
5k=j;
6 while(k<Nmax)
7 if((k!=1)and(k!=i)and(k!=j))
8 MarkComposite(k);
9m=k*i;
10 if(m<Nmax)ts.push_back(k);
11k=m;
12s=ts;ts.resize(0);
13[...]//counting
```
**Algorithm 9** Gale and Pratt sieve

The sieve packs information at the bit level and skips all even candidates, thus a respectable performance and a relatively good memory footprint are obtained from the start.