6
\$\begingroup\$

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);
    }
}
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your suggestions! I'm wondering why you used const auto& lim in for (const auto& lim : inputs) . Why not just auto lim? \$\endgroup\$ – Fhibli Dec 28 '15 at 7:47
  • 1
    \$\begingroup\$ Using const auto & signals the compiler that it doesn' t need to make a copy of the object -- it can essentially just pass a pointer to it. It won't make much difference here, but it can for larger collections of more complex objects, so it's a good habit. \$\endgroup\$ – Edward Dec 28 '15 at 11:25
  • \$\begingroup\$ Oh wow! I knew of the pass by reference but didn't know it could be applied in that situation. Should it be used sparingly in ranged for loops or is it a good rule of thumb to follow? \$\endgroup\$ – Fhibli Dec 28 '15 at 11:27
  • 1
    \$\begingroup\$ The only reason not to use it is if you either want a copy or if the underlying type is primitive. \$\endgroup\$ – Edward Dec 28 '15 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.