# 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 <vector>
#include <algorithm>
#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<big> &p){
big f;
bool n[m];
p={2,3,5};
for(big i=0;i<m;++i)n[i]=true;
for(big i=7,s=1;i<=m;i+=ofs[s],++s==8?s=0:0){
if(!n[i])continue;
p.push_back(i);
for(big j=i,t=s;j<=m/i;j+=ofs[t],++t==8?t=0:0){
if(!n[j])continue;
f=j*i;
do{
n[f]=false;
}while((f*=j)<=m);
}
}
}
inline bool isPrime(big n,std::vector<big> p){
return std::binary_search(p.begin(),p.end(),n);
}
#endif

-
Follow-up question – 200_success May 9 '14 at 1:23

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<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 < 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<=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.

-
This is how my code would normally look, but I really should have cleaned it up if I wanted help, so I've done some of that. – hacatu May 8 '14 at 23:00
Umm... it's a filthy habit to code like that normally. You should aim to write clearly all the time, not just when you expect scrutiny. – 200_success May 8 '14 at 23:02
• The typedef name big makes little sense, especially in regards to integer size. If big can resemble 64-bit, then I suppose bigger can resemble 128-bit.

However, instead of having your own typedef for unsigned long long, use std::uint64_t from <cstdint>, which is guaranteed to be 64 bits on supported implementations. It is preferred to use such integer types from this library. Some additional info about that can be found here.

• There's no practical need for inline, nor will it automatically improve performance. It only serves as a hint to the compiler, and it is still free to ignore it if inlining is unnecessary.

• This code greatly lacks indentation and whitespace. Here are some tips on this:

• Different sections, such as constants and functions, should be separated.
• Although there are no standards in C++ regarding amount of indentation, four spaces is very common and is also quite readable.
• There should be whitespace between operators and operands to help with readability.

Here's an example using one of your statements:

for (big i = 0; i < m; ++i ) n[i] = true;

-