Reduce Prime Sieve Memory Consumption I've made a prime number generator (for Project Euler).  It uses Euler's Sieve (a modified Sieve of Eratosthenes), with a mod 30 step.  I'd like to reduce the memory consumption to 4/15 what it currently is by keeping a boolean array only for the possibly prime remainders of 30.  I can't get it to work and also fear that this will slow down the program.

I've used

n[f/30*8+[zeroes, except 1,2,3,4,5,6,7 at 7,11,13,17,19,23,29][f%30]]


which seemed to not filter out any composite numbers.  How can I make this work and what other optimizations (aside from increasing the mod) can you suggest?  I need the primes up to about two billion.

#include &lt;vector&gt;
#include &lt;algorithm&gt;
#ifndef _pes30_cxx_
#define _pes30_cxx_
typedef unsigned long long big;
const int ofs[]={6,4,2,4,2,4,6,2};
void sievePrimes(big m,std::vector&lt;big&gt; &amp;p){
  big f;
  bool n[m];
  p={2,3,5};
  for(big i=0;i&lt;m;++i)n[i]=true;
  for(big i=7,s=1;i&lt;=m;i+=ofs[s],++s==8?s=0:0){
    if(!n[i])continue;
    p.push_back(i);
    for(big j=i,t=s;j&lt;=m/i;j+=ofs[t],++t==8?t=0:0){
      if(!n[j])continue;
      f=j*i;
      do{
        n[f]=false;
      }while((f*=j)&lt;=m);
    }
  }
}
inline bool isPrime(big n,std::vector&lt;big&gt; p){
  return std::binary_search(p.begin(),p.end(),n);
}
#endif
I consider this to be obfuscated code.  Consider:


There are no comments: no guidance on how to call the function, and no explanation of how it works internally.
All variables have one-character names, as if you had filtered the code through a minifier.  The sole exception is ofs — which is still cryptic and meaningless to me.
You have used nearly the minimum amount of whitespace possible:

SpaceSpacefor(big i=0;i&lt;m;++i)n[i]=true;

The code would be more readable with deeper indentation than two spaces per level.  It would be easier to see the individual parts of the loop header if you put spaces after each semicolon.  The loop body would be easier to see if it didn't immediately follow the closing parenthesis.

    for (big i = 0; i &lt; m; ++i) {
        n[i] = true;
    }


All these changes cost you nothing, and have tangible benefits.
This loop header is trying to accomplish way too much!

for(big j=i,t=s;j&lt;=m/i;j+=ofs[t],++t==8?t=0:0)



Also, why is the code guarded by #ifndef _pes30_cxx_?  Is this code living inside a header file?  If so, move it out to a .cpp file where it belongs.

Given the serious stylistic issues with the code, I doubt that anyone would voluntarily reverse-engineer it and review its substance.  I suggest that you work on expressing yourself clearly, then post a follow-up question asking about memory or other performance concerns.