# Prime Time Tactics--Sieve Tweaks and Boosters
## 2. Sieving Buffer-Related Techniques
### 2.1. Sieve Buffer Structure
* brute-force sieving, using techniques like trial division or other primality testing methods--those should not really be considered sieving techniques. * directly sieving a buffer of candidates using a smaller set of primes to sieve out composites--all the sieves based on classic Eratosthenes, including the linear family of sieves, fall in this category. * Sieve of Atkin--directly sieves a buffer of candidates, but using a number of quadratic forms to establish the primality; nevertheless, in the last step of the sieving process, a small set of primes is still required to sift out efficiently the multiples of squares. - Sieve of Sundaram--indirect sieving: the sieving is carried out using a bilinear form \((2 ij+i+j)\) on a contiguous set and the primes are obtain indirectly from the remainders of that set, after sieving; there are no known methods to reduce the initial contiguous set to be sieved or to reduce the set of factors (the \(i\)s and \(j\)s from the \(2 ij+i+j\) form) involved in sieving--given the current knowledge, it seems that this algorithm can only be optimized at the level of the software implementation. * iterative sieving: Sieve of Pritchard, a case in itself--the sieving is carried out iteratively, on larger and larger sets of candidates, each set being optimally generated in the previous iteration and sieved using the previous set. As we can see, all the practical sieves (Atkin and all SoE-based variants) use a smaller set of prime numbers to sieve out composites; the smallest set of primes necessary to sieve primes up to \(N\) includes all the primes up to \(\sqrt{N}\). We call this set the **root primes**. And, backtracking, to generate the root primes, we need an even smaller set of primes, which we call **seed primes**, up to \(\sqrt{\sqrt{N}}\). For the largest values that are directly manageable by our 64 bit computers (\(N=2^{64}\)), root primes are limited at \(2^{32}\) (a total of 203,280,221 primes) and seed primes at \(2^{16}=65,536\); there is a maximum of 6542 seed primes here, which can be generated extremely fast. Nevertheless, many practitioners prefer to hard-code them in a vector directly in the source code, which is a little dangerous, as one can inadvertently alter a value without noticing, which will result in strange errors. A safer method is to generate the seed primes at compile time, using code like the following:
```
1 constevalautoGenerateSeedPrimesList(void){
2 constexprtprimeLimit=prmsval.lmt[LMT];
3 constexprunsignedtail=limit%root_primorial;
4/add!std!required
5 constexprtprimeise_size=limit/root_primorial+(tail>0);
6 std!arraytplusevelElement,sieve_size>sieve;sieve.fill(0 xF);
7/mm!1 and!nand!nwensoutsidelimitascompesits
8 RESPTb(sieve,1);
9 if(tail>0);
10 for(uint8_t1=0;1<(root_primorial-tail);1++){
11 switch((limit+i)%30)
12{
13 case1:case7:case11:case13:case17:case19:case23:case29:
14 RESETtb(sieve,limit+1);
15}
16}
17}
18
19 tpPrimen=lull+root_sieve_steps[0];
20 uint8_t=1;
21 uint8_tix=1;
22 do{
23 if(GETDR(sieve,n)){
24 tprimenl=n*n;
25 while(root_sieve_values[ix]!-n%root_primorial)
26 IncrementRootIdx(ix);
27 uint8_tj=ix;
28 do{
29 RESETtb(sieve,nil);
30n1+=n*root_sieve_steps[j];
31 IncrementRootIdx(j);) while(ni<limit); } n+=root_sieve_steps[i]; IncrementRootIdx(i); } while(n<ConstSqrt(limit)); constexprunsignedsize-prms_no_lm[LMT]; std:array=uint_6t_size>primes(); tpTimenumPrimes-0; unsignedk; for(n=k-0;k<size>size;k++){ autoProcesBit-[k](constunsignedcharmask,constunsignedcharr) {if(sieve[k]mask)primes[numPrimes+]-(tpRoot)(n+r);}; ProcessBit(1,1);ProcessBit(2,7); ProcessBit(4,11);ProcessBit(0,13); ProcessBit(16,17);ProcessBit(32,19); ProcessBit(64,23); ProcessBit(128,29); n+=root_primorial; }; returnprimes; } constexprautoCACHE_ALIGNseed_primes-GenerateSeedPrimeList<LMT_USED>(); static_assert(seed_primes[1]==11 andseed_primes[prms_no_lm[1]-1]==65521); ```
The clear advantage of such methods is to guarantee either correct values or compiler errors. Another topic is the storage of the root primes.