In answering [this question](https://codereview.stackexchange.com/questions/158381/prime-number-generator-time-limit-exceeded), 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