Sieve of Eratosthenes Given with Range

Question

I'm trying to generate a sequence of prime numbers starting from N to N_Max in C++. My approach is to use Sieve of Eratosthenes to generate these prime numbers:

void runEratosthenesSieve(int upperBound) {
      int upperBoundSquareRoot = (int)sqrt((double)upperBound);
      bool *isComposite = new bool[upperBound + 1];
      memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
      for (int m = 2; m <= upperBoundSquareRoot; m++) {
            if (!isComposite[m]) {
                  cout << m << " ";
                  for (int k = m * m; k <= upperBound; k += m)
                        isComposite[k] = true;
            }
      }
      for (int m = upperBoundSquareRoot; m <= upperBound; m++)
            if (!isComposite[m])
                  cout << m << " ";
      delete [] isComposite;
}

However this function wastes memory by calculating prime numbers 1 to N. Is there a function that will run faster and take up less memory?

You might enjoy my response to [this question](http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes), which generates only the primes on a given range. — user448810, Apr 05 '15 at 16:22

score 1 · Accepted Answer · answered Apr 05 '15 at 11:38

All you need to do is determine if values up to sqrt(N_max) are prime or composite - as you are already doing. Then loop from N to N_max and determine if each value is divisible by the primes found (between 2 and sqrt(N_max)).

That would only be a minor adjustment of your approach.

An aside: rather than using floating point to compute the square root (i.e. sqrt()) , there are simple algorithms for computing the "integer square root" (i.e. given a value M, find the value R which is the largest integer such that R*R <= M). Easily found using your favourite search engine. The advantage is that it gets you away from nuances of floating point, and having to convert back to an integer.

Sieve of Eratosthenes Given with Range

1 Answers1