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?

Answer 1

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.