Is this prime generator inefficient C++?

Question

Is this seen as an in efficient prime number generator. It seems to me that this is pretty efficient. Is it the use of the stream that makes the program run slower?

I am trying to submit this to SPOJ and it tells me that my time limit exceeded...

#include <iostream>
#include <sstream>

using namespace std;

int main() {
    int testCases, first, second, counter = 0;
    bool isPrime = true;
    stringstream out;

    cin >> testCases;

    for (int i = 0; i < testCases; i++) {
        // get the next two numbers
        cin >> first >> second;

        if (first%2 == 0)
            first++;

        // find the prime numbers between the two given numbers
        for (int j = first; j <= second; j+=2) {
            // go through and check if j is prime
            for (int k = 2; k < j; k++) {
                if (j%k == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                out << j << "\n";
            }
            isPrime = true;
        }
        out << "\n";
    }

    cout << out.str();

    return 0;
}

EDIT: The program is supposed to generate prime numbers between the numbers specified in the input. (See here for more details: Prime Generator Problem )

-Tomek

Answer 1

This is one step (skipping even numbers) above the naive algorithm. I would suggest the Sieve Of Eratosthenes as a more efficient algorithm. From the above link:

The complexity of the algorithm is O((nlogn)(loglogn)) with a memory requirement of O(n). The segmented version of the sieve of Eratosthenes, with basic optimizations such as wheel factorization, uses O(n) operations and O(n1 / 2loglogn / logn) bits of memory.

The algorithm you give is somewhere near O(n^2). The speedup you get by skipping evens isn't that great because you would find an even number not to be prime on the first test. The sieve has a much greater memory requirement, but the runtime complexity is far superior for large N.

Answer 2

You're searching a lot more numbers than you have to - at most you only need to go to <= (sqrt(num)).

Answer 3

Here's a simple Sieve of Eratosthenes. It doesn't require predeclaring a big boolean array, but it's still >>O(n) in time and space. As long as you have enough memory, though, it ought to be noticeably faster than what your present naïve method.

#include <iostream>
#include <map>

using namespace std;

template<typename T = int, typename M = map<T, T> >
class prime_iterator {
    public:
        prime_iterator() : current(2), skips() { skips[4] = 2; }
        T operator*() { return current; }
        prime_iterator &operator++() {
            typename M::iterator i;
            while ((i = skips.find(++current)) != skips.end()) {
                T skip = i->second, next = current + skip;
                skips.erase(i);
                for (typename M::iterator j = skips.find(next);
                        j != skips.end(); j = skips.find(next += skip)) {}
                skips[next] = skip;
            }
            skips[current * current] = current;
            return *this;
        }
    private:
        T current;
        M skips;
};

int main() {
    prime_iterator<int> primes;
    for (; *primes < 1000; ++primes)
        cout << *primes << endl;
    return 0;
}

If this is still too slow for you, you may want to pursue the Sieve of Atkin, an optimized Sieve of Eratosthenes.

Actually, these are only relatively efficient if the range of primes to generate starts low. If the lower bound is already fairly large and the upper bound is not much larger than the lower, then the sieving methods are wasteful work and you'd be better off running a primality test.

Answer 4

And one more thing, don't use sqrt(n) in a loop:

for(int k=1;k<sqrt(n);++k)

If there's no good optimization , sqrt will be calculated in every iteration.

Use

for (int k=1;k*k < n;++k)

Or simply

int sq = sqrt ( n );
for (int k=1;k<sq;++k)

Answer 5

It can be made slightly more efficient. You don't need to start k at 2, you're already making sure not to test even numbers. So start k at 3.
Then increment k by 2 every time because you don't need to test other even numbers. The most efficient way that I can think of is to only test if a number is divisible by known prime numbers (then when you find another one add that to the list you test with).

Answer 6

for (int k = 2; k < j; k++) {
     if (j%k == 0) {
         isPrime = false;
         break;
     }
}

should be:

for(int k = 3; k <= j/2; k+=2 )
{
  if( j % k == 0 )
      break;
}

j/2 really should be sqrt(j) but it is typically a good enough estimation.