# Prime Time Tactics--Sieve Tweaks and Boosters
## 2. Sieving Buffer-Related Techniques
### 2.1. Sieve Buffer Structure
Those more than 203 million root primes required to sieve intervals up to 264, if stored in their native form (4 bytes), would take almost 800 MB of memory, which is quite substantial; on the other hand, as the greatest gap between two consecutive primes lower than 232 is 336 (which occurs at 3,842,610,773, the 182,837,804 th prime; the next gap is 354, at 4,302,407,359, the 203,615,628 th prime ([[https://t5k.org/notes/gaps.html](https://t5k.org/notes/gaps.html)]([https://t5k.org/notes/gaps.html](https://t5k.org/notes/gaps.html)), accessed on 11 June 2024)): two bytes would suffice for storing only the gap, considering that this list is always parsed in order so performance reconstituting the primes is not an issue. But then, as all prime gaps are even (except between 2 and 3, the only exception there is, as 2 is the only even prime) and \(336/2<256\), we could store the values halved, using only one byte per gap and thus spending only 194 MB for the root primes, which is especially useful when sieving on GPUs (Graphics Processing Units), where global memory can be an issue. The very simple operations involved here--add, sub, shift--practically do not impact the performance, occupying slots that most probably would be otherwise left unused in the parallel pipeline of the processor. Footnote 4: The code code is available at [[https://github.com/tensorflow/tensorflow/tensorflow/tensorflow/tensorflow](https://github.com/tensorflow/tensorflow/tensorflow/tensorflow/tensorflow)]([https://github.com/tensorflow/tensorflow/tensorflow/tensorflow/tensorflow](https://github.com/tensorflow/tensorflow/tensorflow/tensorflow/tensorflow)). Once we have the sieving buffer and the root primes in place, we can begin the sieving process. However, as any execution profiler will reveal, for any well-optimized implementation, the bottleneck lies not in arithmetic operations but in memory access, specifically memory updates. During the sieving process, the majority of memory updates occur for the smaller prime numbers whose multiples need to be sieved out. For instance, when sieving up to 1000 and skipping over even numbers, the primes 3 and 5 will generate 527 updates, while the prime 7 will generate 136 updates. In contrast, all other root primes will trigger only 248 updates in total. However, the pattern of these updates generated by small primes is repeatable. This exact pattern will repeat identically for each set of \(3\times 5\times 7=105\) values. This period, 105, is the least common multiple (LCM) of the small primes in question, and the period equals the LCM because these numbers, being prime, are all coprime. This repeating pattern is a fundamental property exploited by sieve algorithms, allowing for efficient calculation and elimination of composites. Each time you progress past this interval (in this case, 105), the pattern of multiples that have been marked or eliminated will start over identically. This facilitates the extension of the sieve to larger numbers without rechecking the divisibility by these smaller primes. As you add additional primes, such as 11 and 13, the pattern will extend to 15,015 and reach 255,255 with 17. This characteristic is utilized by many fast sieving implementations through an initial phase typically known as pre-sieving. In this preliminary stage, the pattern is generated in advance, usually at the bit level and going up to 13 or 17. Then, during the main sieving process, this pre-generated pattern is used to initialize the sieve buffer at the start of each iteration. This effectively removes all operations related to the small primes that formed the pattern, streamlining the sieving process.