performance - Is this prime generator inefficient C++? -

is seen in efficient prime number generator. seems me pretty efficient. use of stream makes program run slower?

i trying submit spoj , tells me 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;      (int = 0; < testcases; i++) {         // next 2 numbers         cin >> first >> second;          if (first%2 == 0)             first++;          // find prime numbers between 2 given numbers         (int j = first; j <= second; j+=2) {             // go through , check if j prime             (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: program supposed generate prime numbers between numbers specified in input. (see here more details: prime generator problem )

-tomek

this 1 step (skipping numbers) above naive algorithm. suggest sieve of eratosthenes more efficient algorithm. above link:

the complexity of algorithm o((nlogn)(loglogn)) memory requirement of o(n). segmented version of sieve of eratosthenes, basic optimizations such wheel factorization, uses o(n) operations , o(n1 / 2loglogn / logn) bits of memory.

the algorithm give somewhere near o(n^2). speedup skipping evens isn't great because find number not prime on first test. sieve has greater memory requirement, runtime complexity far superior large n.