Is this prime generator inefficient C++?

#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;
}

#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;
}

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

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

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

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

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