Calculate primes between 'n' and 'm'. Such that n - m = 100000

not_sieve.cc

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main(int argc, char const *argv[])
{
	bool flag;
	int T;
	int m, n;
	int count = 0;
	vector<int> prime_sqrts;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		cin >> n >> m;
		for (int j = 3; j * j<= n; ++j)
		{
			flag = true;
			if(j % 2 == 0)
				continue;
			if(j % 3 == 0 && j != 3)
				continue;
			if(j % 5 == 0 && j != 5)
				continue;
			if(j % 7 == 0 && j != 7)
				continue;
			if((sqrt(j) - (int) sqrt(j)) == 0) {
				prime_sqrts.push_back(sqrt(j));
				continue;
			}
			for (vector<int>::iterator i = prime_sqrts.begin(); i != prime_sqrts.end(); ++i)
			{
				if(j % (*i) == 0 && (*i) != j)
				{
					flag = false;
					break;
				}
			}
			if(!flag)
				continue;
			if(flag) {
				prime_sqrts.push_back(j);
			}
			//cout << "Count:" << count << endl;	
		}
		for (int j = n; j <= m; ++j)
		{
			flag = true;
			if(j < 2)
				continue;
			if(j % 2 == 0 && j != 2)
				continue;
			if(j % 3 == 0 && j != 3)
				continue;
			if(j % 5 == 0 && j != 5)
				continue;
			if(j % 7 == 0 && j != 7)
				continue;
			if((sqrt(j) - (int) sqrt(j)) == 0) {
				prime_sqrts.push_back(sqrt(j));
				continue;
			}
			for (vector<int>::iterator i = prime_sqrts.begin(); i != prime_sqrts.end(); ++i)
			{
				if(j % (*i) == 0 && (*i) != j)
				{
					flag = false;
					break;
				}
			}
			if(!flag)
				continue;
			if(flag) {
				cout << j << endl;
				count++;
			}
				
		}
	}
	
	return 0;
}