fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25. //_ ***************************** START Below *******************************
  26.  
  27.  
  28. int L;
  29. int R;
  30.  
  31. vector<bool> segSeive;
  32.  
  33. void seive(){
  34. 	L = 1e12;
  35. 	R = 1e12+1e6;
  36.  
  37. 	int rootR = sqrt(R);
  38.  
  39. 	vector<bool> isPrime(rootR+1, 1);
  40. 	isPrime[0] = isPrime[1] = 0;
  41.  
  42. 	vector<int> primes;
  43.  
  44.  
  45. 	for(int i=2; i<=rootR; i++){
  46. 		if(isPrime[i] == 0) continue;
  47.  
  48. 		primes.push_back(i);
  49. 		for(int j=i*i; j<=rootR; j+=i){
  50. 			isPrime[j] = 0;
  51. 		}
  52. 	}
  53.  
  54.  
  55. 	segSeive.assign(R-L+1, 1);
  56.  
  57. 	for(auto& p : primes){
  58.  
  59. 		int firstMultiple = ( (L+p-1)/p ) * p;
  60.  
  61. 		int start = max(firstMultiple , p*p);
  62.  
  63. 		for(int j = start; j<=R; j+=p){
  64. 			segSeive[j - L] = 0;
  65. 		}
  66.  
  67. 		if(L == 1) isPrime[0] = false;
  68. 	}
  69.  
  70. }
  71.  
  72. void consistency(int l, int r){
  73.  
  74. 	if(l < L || r > R){
  75.         cout << "Query outside precomputed range\n";
  76.         return;
  77.     }
  78.  
  79. 	for(int i=l; i<=r ; i++){
  80. 		if(segSeive[i-L]) cout << i << " ";
  81. 	}cout << endl;
  82. 	cout << endl;
  83.  
  84. }
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100. void practice(int l, int r){
  101.  
  102.  
  103. }
  104.  
  105.  
  106.  
  107.  
  108.  
  109. void solve() {
  110. 	static int _ = (seive(), 0);
  111.  
  112.     int l, r;
  113.     cin>> l >> r;
  114.  
  115.     consistency(l, r);
  116.  
  117.  
  118. }
  119.  
  120.  
  121.  
  122.  
  123.  
  124. int32_t main() {
  125.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  126.  
  127.     int t = 1;
  128.     cin >> t;
  129.     while (t--) {
  130.         solve();
  131.     }
  132.  
  133.     return 0;
  134. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
2
1000000001910 1000000019100
1000000000030 1000000000150
stdout
copy 
1000000001911 1000000001939 1000000001947 1000000001953 1000000001963 1000000001999 1000000002059 1000000002119 1000000002139 1000000002143 1000000002167 1000000002173 1000000002217 1000000002227 1000000002277 1000000002341 1000000002373 1000000002403 1000000002431 1000000002493 1000000002511 1000000002587 1000000002613 1000000002623 1000000002637 1000000002667 1000000002679 1000000002713 1000000002721 1000000002739 1000000002761 1000000002803 1000000002821 1000000002857 1000000002871 1000000002889 1000000002901 1000000002973 1000000002997 1000000003027 1000000003031 1000000003043 1000000003061 1000000003087 1000000003091 1000000003129 1000000003159 1000000003187 1000000003237 1000000003259 1000000003273 1000000003279 1000000003283 1000000003367 1000000003381 1000000003427 1000000003463 1000000003543 1000000003553 1000000003567 1000000003571 1000000003579 1000000003619 1000000003669 1000000003757 1000000003789 1000000003799 1000000003801 1000000003841 1000000003843 1000000003859 1000000003883 1000000003889 1000000003993 1000000004023 1000000004053 1000000004099 1000000004153 1000000004161 1000000004183 1000000004191 1000000004207 1000000004239 1000000004257 1000000004261 1000000004317 1000000004329 1000000004351 1000000004387 1000000004411 1000000004501 1000000004581 1000000004603 1000000004609 1000000004657 1000000004669 1000000004681 1000000004683 1000000004711 1000000004719 1000000004737 1000000004749 1000000004777 1000000004803 1000000004831 1000000004837 1000000004867 1000000004873 1000000004891 1000000004893 1000000004953 1000000004959 1000000004963 1000000004989 1000000005041 1000000005073 1000000005077 1000000005079 1000000005131 1000000005163 1000000005269 1000000005317 1000000005379 1000000005383 1000000005439 1000000005491 1000000005533 1000000005619 1000000005647 1000000005649 1000000005671 1000000005677 1000000005707 1000000005709 1000000005713 1000000005721 1000000005727 1000000005757 1000000005773 1000000005811 1000000005817 1000000005847 1000000005889 1000000005899 1000000005911 1000000005989 1000000006003 1000000006021 1000000006037 1000000006051 1000000006081 1000000006183 1000000006189 1000000006193 1000000006231 1000000006237 1000000006241 1000000006321 1000000006387 1000000006399 1000000006403 1000000006451 1000000006457 1000000006459 1000000006517 1000000006541 1000000006561 1000000006613 1000000006627 1000000006637 1000000006699 1000000006711 1000000006769 1000000006771 1000000006793 1000000006849 1000000006883 1000000006891 1000000006897 1000000006903 1000000006939 1000000006949 1000000006997 1000000007081 1000000007101 1000000007141 1000000007267 1000000007273 1000000007333 1000000007389 1000000007423 1000000007431 1000000007459 1000000007507 1000000007509 1000000007519 1000000007521 1000000007599 1000000007609 1000000007627 1000000007639 1000000007681 1000000007749 1000000007767 1000000007801 1000000007819 1000000007837 1000000007849 1000000007861 1000000007887 1000000007921 1000000008019 1000000008047 1000000008097 1000000008101 1000000008103 1000000008209 1000000008233 1000000008247 1000000008253 1000000008269 1000000008341 1000000008367 1000000008377 1000000008409 1000000008437 1000000008523 1000000008571 1000000008577 1000000008599 1000000008629 1000000008641 1000000008647 1000000008653 1000000008659 1000000008673 1000000008719 1000000008817 1000000008829 1000000008859 1000000008863 1000000008871 1000000008877 1000000008967 1000000009069 1000000009147 1000000009193 1000000009219 1000000009367 1000000009381 1000000009387 1000000009399 1000000009403 1000000009499 1000000009501 1000000009627 1000000009639 1000000009649 1000000009651 1000000009691 1000000009703 1000000009769 1000000009829 1000000009891 1000000009909 1000000009913 1000000009919 1000000009963 1000000009973 1000000009991 1000000009999 1000000010021 1000000010033 1000000010039 1000000010047 1000000010069 1000000010117 1000000010123 1000000010173 1000000010201 1000000010209 1000000010227 1000000010249 1000000010263 1000000010281 1000000010287 1000000010309 1000000010377 1000000010389 1000000010411 1000000010431 1000000010447 1000000010479 1000000010483 1000000010489 1000000010491 1000000010509 1000000010549 1000000010563 1000000010689 1000000010719 1000000010749 1000000010761 1000000010777 1000000010827 1000000010857 1000000010903 1000000010909 1000000010921 1000000010923 1000000010941 1000000011007 1000000011019 1000000011041 1000000011067 1000000011079 1000000011091 1000000011103 1000000011113 1000000011121 1000000011151 1000000011169 1000000011191 1000000011217 1000000011229 1000000011239 1000000011323 1000000011347 1000000011371 1000000011383 1000000011397 1000000011403 1000000011419 1000000011641 1000000011679 1000000011709 1000000011733 1000000011737 1000000011781 1000000011823 1000000011833 1000000011893 1000000011911 1000000011919 1000000011929 1000000011937 1000000011943 1000000011949 1000000011977 1000000012051 1000000012093 1000000012097 1000000012127 1000000012139 1000000012147 1000000012157 1000000012169 1000000012183 1000000012201 1000000012211 1000000012217 1000000012273 1000000012279 1000000012313 1000000012337 1000000012367 1000000012379 1000000012387 1000000012393 1000000012409 1000000012433 1000000012441 1000000012477 1000000012481 1000000012493 1000000012519 1000000012559 1000000012577 1000000012589 1000000012597 1000000012619 1000000012633 1000000012643 1000000012679 1000000012709 1000000012777 1000000012789 1000000012819 1000000012877 1000000012903 1000000012919 1000000012933 1000000012961 1000000013029 1000000013039 1000000013099 1000000013101 1000000013119 1000000013147 1000000013149 1000000013209 1000000013249 1000000013303 1000000013339 1000000013377 1000000013399 1000000013413 1000000013431 1000000013437 1000000013443 1000000013491 1000000013503 1000000013531 1000000013569 1000000013591 1000000013599 1000000013609 1000000013611 1000000013629 1000000013633 1000000013641 1000000013657 1000000013669 1000000013681 1000000013687 1000000013707 1000000013743 1000000013759 1000000013797 1000000013807 1000000013819 1000000013869 1000000013933 1000000013941 1000000013959 1000000014001 1000000014007 1000000014077 1000000014107 1000000014121 1000000014151 1000000014157 1000000014173 1000000014187 1000000014203 1000000014227 1000000014271 1000000014283 1000000014311 1000000014323 1000000014353 1000000014367 1000000014401 1000000014407 1000000014421 1000000014439 1000000014443 1000000014463 1000000014467 1000000014527 1000000014529 1000000014583 1000000014589 1000000014593 1000000014613 1000000014617 1000000014631 1000000014647 1000000014691 1000000014731 1000000014749 1000000014833 1000000014863 1000000014869 1000000014917 1000000014929 1000000014931 1000000014967 1000000015019 1000000015061 1000000015067 1000000015087 1000000015127 1000000015153 1000000015159 1000000015177 1000000015229 1000000015277 1000000015309 1000000015447 1000000015471 1000000015501 1000000015519 1000000015523 1000000015537 1000000015579 1000000015591 1000000015633 1000000015643 1000000015697 1000000015699 1000000015753 1000000015757 1000000015759 1000000015783 1000000015787 1000000015799 1000000015829 1000000015879 1000000015891 1000000015939 1000000015951 1000000015979 1000000016009 1000000016039 1000000016047 1000000016053 1000000016063 1000000016111 1000000016129 1000000016173 1000000016227 1000000016231 1000000016237 1000000016339 1000000016347 1000000016357 1000000016377 1000000016381 1000000016387 1000000016399 1000000016417 1000000016419 1000000016479 1000000016507 1000000016531 1000000016569 1000000016621 1000000016629 1000000016651 1000000016843 1000000016849 1000000016861 1000000017031 1000000017041 1000000017043 1000000017067 1000000017173 1000000017187 1000000017251 1000000017277 1000000017281 1000000017301 1000000017319 1000000017323 1000000017343 1000000017353 1000000017413 1000000017427 1000000017461 1000000017479 1000000017493 1000000017503 1000000017509 1000000017529 1000000017547 1000000017563 1000000017581 1000000017607 1000000017617 1000000017629 1000000017631 1000000017637 1000000017673 1000000017719 1000000017721 1000000017839 1000000017847 1000000017869 1000000017889 1000000017893 1000000017911 1000000017917 1000000017923 1000000017943 1000000017949 1000000018103 1000000018117 1000000018123 1000000018151 1000000018153 1000000018201 1000000018247 1000000018261 1000000018273 1000000018289 1000000018301 1000000018319 1000000018333 1000000018363 1000000018393 1000000018417 1000000018463 1000000018471 1000000018489 1000000018519 1000000018639 1000000018643 1000000018673 1000000018679 1000000018729 1000000018733 1000000018741 1000000018753 1000000018757 1000000018781 1000000018931 1000000018951 1000000018957 1000000019023 1000000019099 

1000000000039 1000000000061 1000000000063 1000000000091 1000000000121
https://ideone.com/ijaiw8
language:
C++14 (gcc 8.3)
created:
5 seconds ago
visibility:
public

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!