# Prime Number Sieving--A Systematic Review with Performance Analysis
## 3 Outcomes and Discussion
### Classic Sieve Algorithms
#### 3.2.2 From linear to sub-linear
Nevertheless, one can find some very intuitive animation for the Wheel of Pritchard on the internet, for example, at [[https://en.wikipedia.org/wiki/Sieve_of_Pritchard](https://en.wikipedia.org/wiki/Sieve_of_Pritchard)]([https://en.wikipedia.org/wiki/Sieve_of_Pritchard](https://en.wikipedia.org/wiki/Sieve_of_Pritchard)) (accessed on 24 March 2024). The next step is to construct a data structure that is clever enough not to destroy the performance of the sieve. [PERSON]'s idea is to use a single vector \(s\) that keeps all identified \(p_{i}\) in the lower part, and in the rest of the structure, the current \(s_{i}-s\) combines both \(rlink\) and \(llink\) from a double linked list in one vector, capitalizing on the fact that, except 2, even numbers are not prime, so \(s[i]\) will be \(rlink[i]\) and \(s[i-1]\) will be \(llink[i]\). See Algorithm 10 and accompanying code for details. ```
1 uint64_tSoP(uint64_t*s,constuint64_tN)
2{
3 uint64_tmaxS=1,length=2,p=3;
4 autonext=[&&](uint64_tw){returns[w];};
5 autoprev=[&&](uint64_tw){returns[w-1];};
6 autoAppend=[&&](uint64_tw)
7{s[maxS]=w;s[w-1]=maxS;maxS=w;};
8 autoDelete=[&&](uint64_tpf)
9{
10 uint64_ttemp1=s[pf-1];uint64_ttemp2=s[pf];
11s[temp1]=temp2;s[temp2-1]=temp1;
12};
13 autoExtendTo=[&&](uint64_tn)
14{
15 uint64_tw=1;
16 for(uint64_tx=length+1;x<=n;x=length+w)
17{Append(x);w=next(w);}
18 length=n;
19 if(length==N)Append(N+2);
20};
21 autoDeleteMultiples=[&&](uint64_tp)
22{
23 uint64_tf=p;
24 while(p*f<=length)f=next(f);
25 while(f>1){f=prev(f);Delete(p*f);}
26};
27//sieve
28 while(p*p<=N)
29{
30 if(length<N)
31 ExtendTo(std::min(p*length,N));
32 DeleteMultiples(p);
33p=next(1);
34}
35 if(length<N)ExtendTo(N);
36//gettheprimes
37 uint64_tnumPrimes=1;//accountfor2
38 for(p=3;p<=N;p=next(p))numPrimes++;
39 returnnumPrimes;
40}
```
**Algorithm 10** Sieve of Pritchard

The theoretical complexity of SoP is sublinear: \(\mathbf{O(\frac{N}{\ln N})}\), the best one achieved so far. [PERSON] published another meaningful and influential work in 1983 [28], which is important as it formalizes the so-called _static_ or _fixed wheel_ and proves the linear character of the sieve when a static wheel of the order \(k=max(i|P(i)\leqslant(\sqrt{N}))\) is used (\(P\) is the Primorial). The results were somewhat refined by [PERSON] in 1990 [29], and especially in [30; 31]. Moreover, in 1991, [PERSON] showed why SoE is still superior, in practice, to all other theoretically linear algorithms [32]. The timings for a basic but quite large (W8) fixed wheel SoE are given in Table 3--for small values of \(N_{max}\), the total duration is penalized by the time that is necessary to generate the wheel; for middle values, a static wheel can be marginally more efficient than 357, but at very large values, it loses efficiency. To recover, the wheel size must be increased, which adds to the total duration and so on. Several years passed before the next attempt to create something innovative: in 1986, [PERSON] [33] tried to address the problem that all the linear algorithms to date have a fixed superior limit \(N_{max}\) up to which they compute the primes, meaning that if you want to find the next prime number that is greater than \(N_{max}\), you will have to restart the process with another max value, which may not be very convenient. To resolve this, [PERSON] keeps track of the lowest prime factor (\(lpf\)) of composites in a vector that increases incrementally with \(n\)--each number is tested against the previous data, so, theoretically, the algorithm could continue ad infinitinitum. Unfortunately, the performance is not at all satisfactory for large numbers, but the idea is quite beautiful in its simplicity and is worth mentioning: for each odd composite, another, greater composite is stroked out. The underlying idea is that any composite \(n\) can be expressed as \(n=p\times q\), where \(p\) is the lowest prime factor of \(n\).