Ideone.com

fork download

#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
int main()
{
	int a,b,n,i,j,times,lnp,n1;
	n= 31625;
 
	vector<char> prime(n+1,'P');
 
	prime.at(0) = 'N';
	prime.at(1) = 'N';
 
	//Creating list of Primes till n prior to the input scan
	for(i=2;i<=n;i=i+1)
	{
		for(j=i+i;j<=n;j=j+i)
		{
			prime.at(j) = 'N';
		}
	}
	cin >> times ;
	while(times)
	{
		cin >> a;
		cin >> b;
 
		if (a>b)
		{
			times--;
			if (times == 0)
				continue;
			cout << "\n" ;
	           continue;
	    }
	    if ( a <= n && b <= n)
	    {
	    	for(i=a;i<=b;i++)
	    	{
	    		if (prime.at(i) == 'P')
	    			cout << i << "\n" ;
	    	}
	    	times--;
		    if (times == 0)
		    	continue;
		    cout << "\n" ;
		    continue;
	    }
 
		//Finding primes in between the given numbers
		vector<char> checklist((b-a)+1,'P');
		n1 = sqrt(b);
 
		for(i=2;i<=n1;i++)
		{
			if (prime.at(i) == 'P' )
			{
				lnp = (a/i)*i;
				if (lnp == 0 )
					lnp = i;
				else if(lnp == i)
					lnp = lnp + i;
				else if(lnp<a)
					lnp = lnp + i;
				for(j=lnp;j<=b;j=j+i)
				{
					checklist.at(j-a) = 'N';
				}
			}
		}
		for(i=0;i<checklist.size();i++)
		{
			if(checklist.at(i) == 'P' )
				cout << i+a << "\n" ;
		}
 
		times--;
		if (times == 0)
			continue;
		cout << "\n" ;
	}
	return 0;
}

Success #stdin #stdout 0s 3480KB

stdin

2
0 100
1000 5000

stdout

https://ideone.com/Le7Kou

language:

C++ (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language