fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define dbg(var) cout<<#var<<"="<<var<<"\n"
  4. #define ll long long 
  5. #define nl cout<<"\n"
  6.  
  7. ll cil(ll a,ll b){return a/b+(a%b!=0);}
  8. inline ll min(ll a,ll b){return a<b?a:b;}
  9. const int N = 1000000;
  10. ll lp[N+1];
  11. vector<ll>pr;
  12. void sieve(){
  13. 	for (int i=2; i<=N; ++i) {
  14.     if (lp[i] == 0) {
  15.         lp[i] = i;
  16.         pr.push_back (i);
  17.     }
  18.     for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
  19.         lp[i * pr[j]] = pr[j];
  20.    }	
  21. }
  22. bool is_prime[N+10];
  23. int main()
  24. {
  25. 	sieve();
  26. 	int tst;cin>>tst;while(tst--){
  27. 		ll a,b;scanf("%lld %lld",&a,&b);
  28. 		while(a<=min(N,b)){
  29. 			if(lp[a]==a)printf("%lld\n",a);a++;
  30. 		}
  31. 		if(a>b){nl;continue;}
  32. 		int sz=b-a+1;
  33. 		memset(is_prime,1,sizeof is_prime);
  34. 		for(ll p:pr){
  35. 			int start=cil(a,p);//dbg(p);dbg(start);nl;
  36. 			for(int fm=start*p-a;fm<=sz+2 and fm>=0;fm+=p)
  37. 			is_prime[fm]=0;
  38. 		}
  39. 		for(int i=0;i<sz;i++)if(is_prime[i])printf("%lld\n",i+a);
  40.         nl;
  41.  
  42. 	}     		
  43.  
  44. }
Success #stdin #stdout 0.01s 11976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/On6YEB
language:
C++14 (gcc 8.3)
created:
4 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!