fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. ll lim=1000000;
  5. ll p[1000000];
  6.  
  7. void primeSieve()
  8. {
  9.   ll i,j;
  10.   //memset(p,0,sizeof(p));
  11.   for(i=0;i<lim;i++)
  12.   p[i]=0;
  13.   p[2]=1;
  14.   for(i=3;i<lim;i+=2)
  15.   p[i]=1;
  16.  
  17.   for(i=3;i<lim;i+=2)
  18.   {
  19.     if(p[i])
  20.     {
  21.       for(j=i*i;j<lim;j+=i)
  22.       {
  23.         p[j]=0;
  24.       }
  25.     }
  26.   }
  27. }
  28.  
  29. void solve(ll m,ll n)
  30. {
  31. 	//cout<<m<<" "<<n;
  32. 	ll di=n-m+1;
  33.   ll i,j,b[di+1];
  34.   for(i=0;i<di;i++)
  35.   b[i]=1;
  36.  
  37.   for(j=m;j<=n;j++)
  38.   {
  39.         if(j==2)
  40.         continue;
  41.         if(j%2==0)
  42.         {
  43.         	b[j-m]=0;
  44.         }
  45.   }
  46.  
  47.   for(i=3;i*i<=n;i+=2)
  48.   {
  49.   	if(p[i])
  50.   	{
  51.   		for(j=m;j<=n;j++)
  52.       {
  53.       		if(j==i)
  54.     		  continue;
  55. 	        if(j%i==0)
  56. 	        {
  57. 	        	b[j-m]=0;
  58. 	        	//cout<<i<<" "<<j<<"\n";
  59. 	        }
  60.       }
  61.   	}
  62.  
  63.   }
  64.   if(m==1)
  65.   {
  66.     b[0]=0;
  67.   }
  68.  
  69.   for(i=m;i<=n;i++)
  70.   {
  71.     if(b[i-m]==1)
  72.     {
  73.       cout<<i<<"\n";
  74.     }
  75.   }
  76. }
  77.  
  78. int main() {
  79.   ios_base::sync_with_stdio(false);
  80.   cin.tie(NULL);
  81.   ll t,m,n,i,j;
  82.   cin>>t;
  83.   primeSieve();
  84.   while(t--)
  85.   {
  86.     cin>>m>>n;
  87.     solve(m,n);
  88.     cout<<"\n";
  89.   }
  90.   return 0;
  91. }
Success #stdin #stdout 0s 23048KB
comments (?)
stdin
copy 
2
5 10
11 20
stdout
copy 
5
7

11
13
17
19
https://ideone.com/NpH1Th
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 years ago
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!