# Prime Number Sieving--A Systematic Review with Performance Analysis
## 3 Outcomes and Discussion
### Classic Sieve Algorithms  
#### 3.2.1 Days of Yore  
The first mention we found of a computer algorithm being used to generate primes dates to more than 60 years ago [13]. The topic was submitted by [PERSON] in 1961 as a very short article: a third of a column on a two-column page in _Communications of ACM_ journal, containing less than 50 words of text plus 9 lines of archaic code, with _labels_ and _gotos_. The algorithm, called **Algorithm 35: Sieve**, was described as using the Sieve of Eratosthenes, but is actually it a brute-force, trial-division-based sieve--as memory was a very scarce resource for computers, this approach was more realistic, although much heavier in terms of complexity [8]. Still, we can identify two of the main optimization points that differentiate a basic but sound SoE implementation from a naive one: skipping even numbers and processing primes only up to \(\sqrt{N}\)--we shall call these first \(\pi(\sqrt{N})\) primes _the root primes_. Two re-visitations of **Algorithm 35** were published in the following year ([14,15]), proving that the generation of prime numbers was a topic of interest. The next articles about prime sieving appeared in 1967, when [PERSON] published **Algorithm 310: Prime Number Generator 1**[16] and **Algorithm 311: Prime Number Generator 2**[17]. [PERSON] tried to find innovative techniques that would use as little RAM as possible--his idea was to advance with all the primes' multiples in parallel and as in sync as possible, instead of processing each one separately and sequentially. Basically, [PERSON] reversed the logic of SoE, condensing the repeated sweeps of the original in a single, unified wave--we call this orchestrated tide of multiples _the front-wave_, and each number that is not touched by the front-wave is a prime. The list of candidates is parsed only once, in strict order, so there is no need to store it in the memory. However, we need to keep two parallel lists: one for the primes themselves; one for the current multiples. [PERSON] exploited two main sieving optimization tips: (1) for each \(p\) in the root primes, we need to sweep only from \(p^{2}\) up, and (2) we can skip over some classes of candidates and multiples of \(p\) to avoid a lot of useless operations--[PERSON] skips multiples of 2 and 3 by cleverly alternating between steps 2 and 4, thus hitting only candidates and multiples in the form \(n=6k\pm 1\). The front-wave idea is introduced in Generator 1 and then optimized in Generator 2 by implementing the \(6k\pm 1\) pattern and keeping the front-wave ordered (using merge sort) to avoid repeated full scans. [PERSON] followed this up in 1969 with **Algorithm 356**[18], an optimized version of Generator 2--using a pragmatic tree/heap sort, he streamlined a lot of the complications [PERSON] used to maintain the front-wave order (see Algorithm 5). ```
1. Initialize two vectors: IQ, the front-wave vector (the current multiples of root primes) organized as a heap, and IQ, a parallel vector with the information for the next step: \(\times 2\) if negative, \(\times 4\) if positive
2. Initialize \(iqi\) and \(jqi\), the values corresponding to the current smallest element in the front-wave (they are not kept in the heap)
3. For each candidate, \(n<Nmax\)
4. If \(n=iqi\) (\(\Rightarrow\)\(n\)\(\in\)\(composite\))

\(\bullet\) While \(n=iqi\), advance \(iqi\) to the next value, keeping the heap ordered
5. Otherwise, (\(\Rightarrow\)\(n\)\(\in\)\(prime\))

\(\bullet\) If \(n<\sqrt{Nmax}\) add \(n*n\) to the heap, keeping the heap ordered
```  
**Algorithm 5** Chartres' Generator 2--[PERSON] 356 optimized version  
Formula (7) was not known in 1967, but is very useful when striving to obtain a more economic sizing of pre-allocated vectors IQ and IQ, Anyway, the space complexity of this algorithm is quite interesting for its class.