patterncppMinor

Reduce Prime Sieve Memory Consumption

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

sievereducememoryprimeconsumption

Problem

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 
#include 
#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 &p){
  big f;
  bool n[m];
  p={2,3,5};
  for(big i=0;i p){
  return std::binary_search(p.begin(),p.end(),n);
}
#endif

Solution

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:

SpaceSpace

for(big i=0;i

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

Code Snippets

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

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

Context

StackExchange Code Review Q#49275, answer score: 4

Revisions (0)

No revisions yet.