Prime Numbers (SPOJ)

prime.cpp

// https://www.spoj.pl/problems/PRIME1/
//http://www.swageroo.com/wordpress/spoj-problem-2-prime-generator-prime1/
#include <iostream>

using namespace std;

int main(){
	int count;
	cin >> count;
	while(count--){
		int upper, lower;
		cin >> lower >> upper;

		int *notPrimes = new int[upper-lower+1];
		for (int i = 0; i < upper-lower+1; i++)
			notPrimes[i] = 0;

		for (int p = 2; p*p <= upper; p++){
			int i = lower/p;
			i *= p;

			for (; i <= upper; i += p){
				if (i >= lower && i != p)
					notPrimes[i-lower] = 1;
			}
		}

		for (int i = lower; i <= upper; i++){
			if (i != 1 && notPrimes[i-lower] == 0)
				cout << i << endl;
		}

		delete[] notPrimes;
		cout << endl;
	}

	return 0;
}