Object oriented, runtime expandable Sieve of Eratosthenes

In answering this question, it seemed to me that it would be nice to have a runtime expandable Sieve of Eratosthenes. This is my implementation of that notion.

Design

I've created a class named Sieve which has two member functions:

unsigned Sieve::expand(unsigned upperlimit);

This expands the existing sieve up to the passed upper limit and attempts to minimize rework. That is, if the current sieve has an upper limit of 10 and the expansion request is 15, the code only processes the difference, i.e. the half open range (10, 15]. If the new requested limit is smaller, the code simply returns without doing anything.

The other significant function is:

bool isPrime(unsigned n) const;

As one would expect, if n is not greater than the current upper limit, the returned bool is true if n is prime. If n is greater than the current limit, this function throws a std::range_error. The intent is that one could either catch an error or, better, always call expand before isPrime. The reason for not combining those within the class code is that I wanted to create a complete but minimal interface.

The test code is simply a reinterpretation of the original code's interface. Specifically, it expects one integer to be the number of test cases, T, and then for each test case, a lower and upper integer (m, and n). For each test case, the code prints a list of prime numbers in the range [m, n] separated by spaces. The test code assumes correct input and does not, for example, check to assure that m < n.

primes.cpp

```
#include
#include
#include
#include
#include

class Sieve {
public:
Sieve();
unsigned expand(unsigned upperlimit);
bool isPrime(unsigned n) const;
private:
unsigned limit;
std::vector composite;
};

Sieve::Sieve() :
limit{0},
composite{}
{}

bool Sieve::isPrime(unsigned n) const {
if (n > limit)
throw std::range_error("n must be less than limit");
return n==2 || (n%

Initialize your class members in the declaration

class Sieve {
public:
    unsigned expand(unsigned upperlimit);
    bool isPrime(unsigned n) const;
private:
    unsigned limit = 0;
    std::vector composite{};
};

is easier to read because you don't need to jump to the constructor to see the initial values and now you don't even need a constructor anymore.

In case you do write constructors and use the initialization list syntax it will override the declaration initialization for those members, so your constructors can concentrate on initializing members that are different than the default from the declaration, again increasing readability.

Limit your nesting depth

Sieve::expand is moving quite far to the right. A way to avoid that is to use early exits instead of nesting:

unsigned Sieve::expand(unsigned upperlimit) {
    if (upperlimit <= limit)
        return limit;
    composite.resize(upperlimit);
    composite[0] = true; // 1 is not prime
    const unsigned sqrtLimit = std::ceil(std::sqrt(upperlimit));
    // std::cout << "old limit = " << limit << ", new limit = " << upperlimit << "\n";
    for (unsigned i = 3; i <= sqrtLimit; i += 2) {
        if (composite[i / 2])
            continue;
        const unsigned start = i * std::max(i, (((limit + i) / i) | 1));
        // std::cout << "Starting with i = " << i << ", from " << start << "\n";
        for (unsigned j = start; j <= upperlimit; j += i + i) {
            composite[j / 2] = true;
            // std::cout << j << " is composite because it's a multiple of " << i << "\n";
        }
    }
    limit = upperlimit;
    return limit;
}

Declare variables as late as possible

Inside main you don't need m and n until you are inside the for loop.

Do at least basic input error checking

You wrote that the program expects valid input, but that is not really acceptable. When a user enters something that cannot be parsed as an int you read uninitialized memory which is undefined behavior and bad things happen.

if (!(std::cin >> m >> n)) return -1; at least gives your program defined behavior without much effort. You could also throw an exception or print a proper message and let the user try again, but having std::cin outside an if is usually a problem.

Better name-giving-ness

limit and upperlimit seem less nice than size and requested_size.
T is usually a template parameter and it probably shouldn't be the only variable name that is capitalized. m and n don't tell me much either. I would prefer T-> test_cases, n->upper, m->lower or something more descriptive.

Consistent parenthesis for ifs

Arguably it is a matter of style if you prefer

if (n > limit) 
        throw std::range_error("n must be less than limit");

or

if (sieve.isPrime(i)) {
    std::cout << i << ' ';
}

but you should pick a style and stick to it.
Now, going through the code and adding brackets around one-line if-statements is a stupid waste of time, fortunately clang-tidy -fix .cpp "-checks=-,readability-braces-around-statements" -- -std=c++14 can automatically fix that for you.

StackExchange Code Review Q#158503, answer score: 4