PRIME1.cpp

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

void printPrimes(int start, int finish)
{
	int length = finish+1;
	int upperBoundSqrt = (int) sqrt((double)finish); // compute limit to marking off primes
	bool primes[length];
	// memset(primes, true, sizeof(bool) * length);
	for(int i=0; i<length; i++) primes[i]=true;
	for(int i=2; i<=upperBoundSqrt; i++)
	{
		if(primes[i] && i>=start)
			cout << i << endl; //print out prime before marking off its multiples
		for(int j=i; j<=finish; j+=i) primes[j]=false;
	}
	for(int i=upperBoundSqrt; i<=finish; i++)
		if(primes[i])
			cout << i << endl;
}

int main(void)
{
	int number, start, finish;
	cin >> number;
	for(int i=0; i<number; i++)
	{
		cin >> start;
		cin >> finish;
		printPrimes(start, finish);
		if(i+1!=number) cout << endl;
	}
}