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.
//pes30.cxx
#include <vector>
#include <algorithm>
#ifndef _pes30_cxx_
#define _pes30_cxx_
typedef unsigned long long big;
const int offsets[]={6,4,2,4,2,4,6,2};
//fill a given vector with all primes under some value:
void sievePrimes(big max, std::vector<big> &p){
big multiple;
bool n[max];//array of whether or not each number is prime (30/8 too big!)
p={2,3,5};//because the sieve skips all multiples of 2,3, and 5, start with them.
for(big i=0; i<max; ++i)//initialize the array
n[i]=true;
//for every number marked prime less than max, mark its multiples with
// every number still marked prime over it as composite.
for(big i=7, step=1; i<=max; i+=offsets[step], ++step==8?step=0:0){
if(!n[i])//if i is not prime
continue;
p.push_back(i);//add i to the list of primes
//finds every multiple of i and a (still marked) prime greater than i
for(big j=i, step2=step; j<=max/i; j+=offsets[step2], ++step2==8?step2=0:0){
if(!n[j])//skip nonprimes
continue;
multiple=j*i;//begin at i^2
do{
n[multiple]=false;
}while((multiple*=j) <= max);
}
}
}
//test if a number is prime by searching a given list of primes for it:
inline bool isPrime(big n, std::vector<big> p){
return std::binary_search(p.begin(), p.end(), n);
}
#endif
Note that this is a re-post with ... proper formatting, and while I appreciate critiques of my coding style, I would also appreciate some advice about improving the array as well (storing only numbers n with n mod 30 prime or 1, but not 2, 3, or 5).