# Prime Number Sieving--A Systematic Review with Performance Analysis
## 3 Outcomes and Discussion
### Mathematical Roots of Sieving for Primes  
A **prime number** is a number that has exactly two divisors: 1 and itself (1 is not a prime number; 2 is the only even prime number). A number that is not prime is called **composite** and can be expressed as a unique product of prime numbers. Two numbers \(a\) and \(b\) are **coprime** if they have no common divisor greater than 1 (\(\text{GCD}(a,b)=1\)). All sieving algorithms work exclusively with positive integers. _Sieve Theory_ was ignited by [PERSON] sieve (SoE) for prime numbers and obtained a life of its own, with ambitions far surpassing the \"simple\" process of sifting for primes [7]. However, SoE remains the most popular sieving technique--see Algorithm 2. ```
1. Initialize a list with all the possible candidates (i.e., the numbers from 2 up to the maximum value N we are looking for);
2. Remove from the list all the multiples of the first number in the list that has not yet been visited;
3. Repeat step 2 until we reach the end of the list;
4. The remaining numbers in the list are all the prime numbers lower than N.
```  
**Algorithm 2** Basic SoE algorithm  
As explained in [8], the complexity of SoE is as follows:  
\[\mathbf{C}(SoE)=\mathbf{O}(N\ln(\ln(N))) \tag{1}\]  
based on [PERSON] theorem [9]:  
\[\sum_{p\;\leqslant\;x}\left(\frac{1}{p}\right)\approxeq\ln(\ln(x))\quad(\leftarrow \text{where $p$ is prime}) \tag{2}\]  
[PERSON] postulates that this partial sum of the reciprocals of the first prime numbers [10] is the logarithm of the associated harmonic series. The relation between [PERSON]'s _zeta function_ (for \(s=1\)) and the identity proved by [PERSON] is shown as follows:  
\[\zeta(s)=\sum_{n=1}^{\infty}\left(\frac{1}{n^{s}}\right)=\prod_{p}\left(\frac {1}{1-p^{-s}}\right)\quad(\leftarrow\text{where $p$ is prime}) \tag{3}\]  
This is important in our context because, in that proof, [PERSON] implicitly used an improved version of SoE: the Sieve of Euler (SoE+). While SoE computes more multiples than required, SoE+ will compute exactly as many multiples are required to eliminate all composites from the list--see Algorithm 3. ```
1. Create a list A with all the numbers from 2 up to the maximum value N, plus an empty list B for the primes;
2. Mark down for removal from list A all the numbers equal to the product of the first number in the list, multiplied with each number remaining in the list, including itself;
3. Remove from list A all marked numbers;
4. Move the first number from list A in list B;
5. Repeat from step 2 until list A is empty;
6. List B contains now all the primes lower than N.
```  
**Algorithm 3** Basic SoE+ algorithm  
Ignoring the overhead, there is exactly one main complex operation per number (either mark and remove the number from the primary list or move it to the primes list), meaning that this technique is linear:  
\[\mathbf{C}(SoE+)=\mathbf{O}(N) \tag{4}\]  
It is known that [PERSON] used a version of the product above (3) to prove the infinitude of prime numbers, which is related to the problem of counting all the prime numbers lowerthan \(x\)--we call this number \(\pi(x)\). First, [PERSON] stated the existence of a relationship between \(\pi(x)\) and \(\frac{x}{ln(x)}\)[8], then both [PERSON] and [PERSON] established more precise formulas: in general, for large numbers, we can approximate the following formula (called _Prime Number Theorem_[8]):  
\[\pi(x)\,\approx\,\frac{x}{\ln(x)} \tag{5}\]  
Where required, more precise approximations for the upper and lower bounds were given by [PERSON] [11]:  
\[\frac{x}{\ln(x)}\bigg{(}1+\frac{0.992}{\ln(x)}\bigg{)}\leqslant\pi(x)\quad( \leftarrow\text{ where }x\geqslant 599) \tag{6}\]  
and  
\[\pi(x)\,\leqslant\,\frac{x}{\ln(x)}\bigg{(}1+\frac{1.2762}{\ln(x)}\bigg{)} \quad(\leftarrow\text{ where }x>1) \tag{7}\]  
Last formula (7) is very useful to obtain minimal yet sufficient vector sizes in various algorithms.