Returns all primes p between m <= p <= n

Question

This is my submission for the Prime Generator on SPOJ and it was accepted. Are there any improvements/changes I can make?

Input:

The input begins with the number \$t\$ of test cases in a single line (\$t \le 10\$). In each of the next t lines there are two numbers \$m\$ and \$n\$ (\$1 \le m \le n \le 1000000000\$, \$n-m \le 100000\$) separated by a space.

Output:

For every test case print all prime numbers \$p\$ such that \$m \le p \le n\$, one number per line, test cases separated by an empty line.

Example:

Input:

2
1 10
3 5

Output:

2
3
5
7

3
5

---

#include <iostream>
#include <cmath>
#include <vector>

using std::vector;
using std::cout;
using std::cin;

bool isPrime(int n) {
    if (n == 1) return false;
    if (n == 2) return true; // invariant
    int root = int(ceil(sqrt(n))); // check up to ceil of square root n
    for (int i = 2; i <= root; ++i){
        if (n % i == 0) return false; // not prime 
    }
    return true;
}


int main() {
    int lines;
    int toPush;
    vector<int> inputs;
    // get inputs
    cin >> lines;
    int tempA = 0;
    while (tempA < 2*lines) {
        cin >> toPush;
        inputs.push_back(toPush);
        ++tempA;
    }

    auto i = inputs.begin();
    while (i < inputs.end()){
        int m = *i;
        int n = *(i + 1);
        while (m <= n){
            if (isPrime(m)){
                int value = m;
                cout << value << " ";
            }
            ++m;
        }
        cout << "\n";
        std::advance(i, 2);
    }
}

Answer 1

Here are a few things that may help you improve your program.

Improve your algorithm

Right now, within the isPrime routine, the loop begins at 2 and does a test division of every number from \$2\$ to \$\sqrt{n}\$. However, we already know that other than 2, all prime numbers are odd. You can approximately double the speed of this algorithm by writing it like this instead:

bool isPrime(int n) {
    if (n == 1) return false;
    if (n == 2) return true; 
    if (n % 2) return false;
    int root = int(ceil(sqrt(n))); 
    for (int i = 3; i <= root; i+=2){
        if (n % i == 0) return false; 
    }
    return true;
}

Prefer for to while where appropriate

The input section of the code has these lines:

int tempA = 0;
while (tempA < 2*lines) {
    cin >> toPush;
    inputs.push_back(toPush);
    ++tempA;
}

It seems to me that this would be more clear as a for loop:

for(int tempA = 2*lines; tempA; --tempA) {
    std::cin >> toPush;
    inputs.push_back(toPush);
}

The same is true for the main loop in the program. It could be written this way:

for (auto i = inputs.begin(); i != inputs.end(); ++i) {
    for (int m = *i++, n=*i; m <= n; ++m) {
        if (isPrime(m)){
            std::cout << m << " ";
        }
    }
    std::cout << '\n';
}

Store std::pairs instead of ints

After the first number, the program's input consists of pairs. It might make more sense to store them in a std::vector<std::pair<int, int>>

The input routine would then look like this:

for(int tempA = 2*lines; tempA; --tempA) {
    std::pair<int, int> toPush;
    std::cin >> toPush.first >> toPush.second;
    inputs.push_back(toPush);
}

The main loop is then considerably simplified by the use of the pair and a "range-for" outer loop:

for (const auto &lim : inputs) {
    for (int m = lim.first; m <= lim.second; ++m) {
        if (isPrime(m)){
            std::cout << m << " ";
        }
    }
    std::cout << '\n';
}

}

Use a better algorithm

The code works as it is, but could be still further improved. Since the inputs are all read at the beginning, you could choose the largest upper bound and run a sieve of Eratosthenes to derive all primes up to that number. Then printing for any range would be simply a matter of lookup.