views:

1236

answers:

6

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

+11  A: 

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.

Matt J
that may not be possible in available memory, however; setting up an array of size INTMAX then canceling the unused items take a lot of RAM; certainly it can be done with a linked list, but that's slow, too
warren
You really only need one bit per number to implement that algorithm.
Ferruccio
For the purposes of SPOJ, I doubt they would make second-first so large that memory would be an issue, and if they did, they would probably be pretty lenient with runtime. In general, SPOJ will force you to choose a runtime-efficient, if not memory-efficient, algorithm to complete in time.
Matt J
+6  A: 

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

warren
Is this true? If I need to find the primes between 1 and 9, how would I find 5 and 7 if I only tested up to 3? Are you thinking of factorization?
Matt J
He means in the loop where 2 <= k < j it should be bounded 2 <= k <= sqrt(j).
Greg Rogers
Got it. That's embarassing ;-)
Matt J
sorry - I should have been clearer on my phrasealogy
warren
A: 

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

jsl4980
In the same idea, only 6k+1 and 6k+5 can be primes.
Luc Hermitte
A: 
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.

Austin Salonen
sqrt(j) is way better than j/2 even at a modest j of 100.
Anthony Potts
+1  A: 

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.

ephemient
+1  A: 

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)
dpetek