Object oriented, runtime expandable Sieve of Eratosthenes

Question

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 <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdexcept>

class Sieve {
public:
    Sieve();
    unsigned expand(unsigned upperlimit);
    bool isPrime(unsigned n) const;
private:
    unsigned limit;
    std::vector<bool> 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%2 && !composite[n/2]);
}

unsigned Sieve::expand(unsigned upperlimit) {
    if (upperlimit > 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]) {
                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;
}

int main() {
    int T;
    int m, n;
    Sieve sieve;

    for (std::cin >> T; T; --T) {
        std::cin >> m >> n;
        sieve.expand(n);
        for (int i = m; i <= n; ++i) {
            if (sieve.isPrime(i)) {
                std::cout << i << ' ';
            }
        }
        std::cout << '\n';
    }
}

Results

When compiled on my 64-bit Linux machine with this command:

g++ -O2 $CXXFLAGS primes.cpp -o primes

I can then run and time the program with this:

time echo 4 1 13 40 50 80 90 10000000 10000100| ./primes 

Here is the output:

2 3 5 7 11 13 
41 43 47 
83 89 
10000019 10000079 

real  0m0.044s
user  0m0.041s
sys   0m0.004s

Answer 1

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