RE: Datatypes for sieve algorithms

[Jacques Gélinas <jacquesg00@hotmail.com>]

{ The algorithm in question is the sieve of S.P. Sundaram, an Indian 
  mathematician who discovered it in 1934. It is proven correct
  in http://en.wikipedia.org/wiki/Sieve_of_Sundaram }

Still, the sieve implementation in PARI/GP raises some
questions for me, particularly concerning memory. 
While PARI/GP only needs 16MB for 1,048,576 primes,

NP = 2^20;
GP = primes_zv(NP);

the working vector P has 8,501,423 elements
and the stack now grows to 128MB. 

N = (GP[NP]-1)/2;
P = vectorsmall(N,n,2*n+1);

However, only one bit per integer is in fact needed to test 
the Sundaram algorithm, which means only ~1MB.
The sieve operations should involve offset calculations
and bitset/bittest operations only.

my(l=1,m); for(k=1,(N-1)/3, l+=2; m=k; for(j=1,(N-k)/l, m+=l; P[m] = 0 ));
MP = N + 1 - vecsum(apply(n->!n,Vec(P))); \\ 256MB !!!
Q = vectorsmall(MP); Q[1]=2;
m=1; for(n=1,N,if(P[n],Q[m++]=P[n]));
Q == GP  

Jacques Gélinas, Ottawa