# Prime Time Tactics--Sieve Tweaks and Boosters
## 2. Sieving Buffer-Related Techniques
### 2.1. Sieve Buffer Structure
A very clever solution for the \(6k\pm 1\) pattern is to use the fact that the distance between each of two consecutive values alternates the step between 2 and 4; thus, in loops, we can always manage it like this (as introduced in [6]):
```
for(n=5,step=2;m<=max;m++step,step=6-step) \(\times\)/sieveforn \(\gamma\)
```
Yet, this straightforward loop-based approach is not always applicable; most algorithms require the numeric values to be converted into into buffer indexes and back, and here, logico-arithmetic functions like the following were the rule:
```
//straightforward template<classT> inlineconstexprTval2 idx(Tn) { T k=n-1; if(k%6==0)returnk/3;//6k+1  k=n-1; if(k%6==0)return(k/3)-1;//6k-1  assert(false); return0; }; //optimized template<classT> inlineconstexprTval2 idx(Tn) { auto minus1-D[Tv]{returnv-1}; autoplus1-D[Tv]{returnv+1}; return(minu1(n)%6==0)*(minu1(n)/3)+//6k+1 (plus1(n)%6==0)*(plus1(n)/3-1);//6k-1 };
```
But even these optimized accessors are quite heavy, and for this we devised the following versions for the \(6k\pm 1\) pattern that are extremely light in comparison :
```
autoidx2 no.6k=D[](uint64 idx){ return3*idx+5-(idx&1);}; autono2 idx.6k=D[](uint64 no){ returnno3-1;1;}
```
We attempted to apply this approach to the \(30k+i\) pattern, but achieved only partial success:
```
autoidx2 no.30k=[](uint64 idx){ uint64k-idx/8; return4*(G+1/6)+7-2*(1/2+1/7)+30*k;}
```
All the operations involving powers of two are very well optimized by the compiler; there are only two divisions that look difficult, but those are divisions by constant and, again, the optimizing compiler will transform them in very fast shift/mul ops. This arithmetic function is six times faster than the logical variant, but unfortunately we failedto come up with a reasonable inverse one; still, we are certain that somebody can do much better than this. Our main contribution regarding sieve buffer structure was to introduce, substantiate, and generalize an approach based on residual classes to the sieving buffer and to the sieving process in general. Inspired by the Sieve of Atkin (SoA), where different quadratic forms are employed for different residual classes of 12, the initial idea was to process each of these residual classes separately and in parallel; the next step, to also differentiate the buffer per residue class, was immediate, resulting in four distinct buffers for SoA, corresponding to the four residual classes of interest: 1 (mod 12), 5 (mod 12), 7 (mod 12), and 11 (mod 12). As explained in [23], this approach not only compresses the buffers for even better cache intensity and facilitates the parallelism of the algorithm, but also has an impact on the number of operations itself, as the modulo arithmetic simplifies the operations and helps reduce the set of sieving numbers. An extension of this idea to the classic wheel of 3 (W3 = {1,7,11,13,17,19,23,29})) was introduced in [24] and was generalized in the same paper as the vertical sieve, as illustrated in Figure 1 for W3. The generalized vertical sieve works on distinct buffers, one for each residue class corresponding to the members of a wheel (wheel values). W3 has eight members, and thus eight buffers. W5 has 480, and W7 already has 92,160 members. The next one, W8, does not seem to be practical anymore, with more than 1.5 million members. While the basic sieving operations are somewhat simplified by the modulo arithmetic, when it comes to segmenting the sieve, the initial positioning for each segment is more cumbersome; the same paper [24] gives a generic solution for this problem and provides a very fast implementation up to W7, which, benchmarked against **primesieve**[25]--the current golden standard in sieving--demonstrates the efficiency of the vertical sieve. ### Sieving

Analyzing all the sieving algorithms known so far, as presented in [22], there are several distinct sieving strategies that emerge:

Figure 1: Normal versus vertical sieves.