Help decoding Yarin sieve

Revision en2, by RNR, 2019-07-11 21:18:06

I know the standard sieve algorithm for finding primes in a range [0..upperbound]

Here is a standard implementation

for(int i=2;i<=N;i++) 
    if(prime[i])
        for(int j=i*i;j<=N;j+=i) prime[j]=0;

But when memory is tight, here is the famous implementation by yarin

#define MAXSIEVE 100000000 // All prime numbers up to this
#define MAXSIEVEHALF (MAXSIEVE/2)
#define MAXSQRT 5000 // sqrt(MAXSIEVE)/2
char a[MAXSIEVE/16+2];
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd

int i,j;
memset(a,255,sizeof(a));
a[0]=0xFE; // 254
for(i=1;i<MAXSQRT;i++)
  if (a[i>>3]&(1<<(i&7)))
    for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)
      a[j>>3]&=~(1<<(j&7));

I understood that we are only storing odd numbers and char can store 8 bits and we are storing it using j>>3 and unsetting using ~(1<<(j&7)). When considering only odd numbers, you let index 1 be 3, index 2 be 5 etc.

But I didn't understand the strange loop incrementations and initialization in for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)

Any help would be greatly appreciated. Thank you in advance.

Tags #sieve, sieve of eratosthenes, sieve

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English RNR 2019-07-11 21:18:06 77
en1 English RNR 2019-07-11 19:31:11 1097 Initial revision (published)