Function main

Spoj_problems/PRIME1/solution.cpp:43–91

}

int main()
{
	int T;//the number of test cases
	cin>>T;
	int i,p=0,s;

	int N;//larger number
	int M;//smaller number
	bool primesNow[DIFF_SIZE];

	while(T--)
	{
		cin>>M>>N; //input the range

		for(i=0;i<DIFF_SIZE;i++)
		primesNow[i]=true;  //initialise to all true . we will mark the composite number as false and then
		//the remaining true numbers will be prime

		populateMyPrimes(N); //this populates the primes in sqrt(N) in an array myPrimes

		for(i=0;i<cnt;i++)  //for each prime in sqrt(N) we need to use it in the segmented sieve process
		{
			p=myPrimes[i]; //store the prime
			s=M/p;
			s=s*p; //the closest number less than M that is a composite number for this prime p

			for(int j=s;j<=N;j=j+p)
			{
				if(j<M) continue; //because composite numbers less than M are of no concern to use.
				primesNow[j-M]=false;//j-M = index in the array primesNow,this is because max index allowed in the array
				//is not N ,it is DIFF_SIZE so we are storing the numbers offset from M
				//while printing we will add M and print to get the actual number
			}
		}

		for(int i=0;i<cnt;i++)     //in the above loop the first prime numbers for example say 2,3 are also set to false
		{                          //hence we need to print them in case they  are within range.
			if(myPrimes[i]>=M && myPrimes[i]<=N) //without this loop you will see that for an range(1,30), 2 and 3 does
				cout<<myPrimes[i]<<endl;         //not get printed
		}

		for(int i=0;i<N-M+1;++i) // primesNow[]=false for all composite numbers,so prime numbers can be found by checking with true
		{
			if(primesNow[i] == true && (i+M)!=1) //i+M != 1 to ensure that for i=0 and M=1 , 1 is not considered a prime number
				cout<<i+M<<endl; //print our prime numbers in the range
		}
	}
	return 0;
}