fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef vector<int> vi;
  5. typedef priority_queue<int> maxHeap;
  6. typedef priority_queue<int, vector<int>, greater<int>> minHeap;
  7. #define inputArray(a, n) \
  8.     for (int i = 0; i < n; i++) cin >> a[i];
  9. #define printArray(a, n) \
  10.     for (int i = 0; i < n; i++) cout << a[i] << endl;
  11. typedef pair<int, int> pii;
  12. #define endl "\n"
  13. #define PB push_back
  14. #define MP make_pair
  15. #define FF first
  16. #define SS second
  17. #define int long long
  18. #define MOD 1000000007
  19. #define PI 3.1415926535897932384626433832795
  20. #define clr(val, val1) memset(val, val1, sizeof(val))
  21.  
  22. void __init() {
  23.     ios_base::sync_with_stdio(0);
  24.     cin.tie(0);
  25.     cout.tie(0);
  26. #ifdef LOCAL
  27.     freopen("input.txt", "r", stdin);
  28.     freopen("output.txt", "w", stdout);
  29. #endif
  30. }
  31.  
  32. const int N = 100000;
  33.  
  34. bitset<N> b;
  35. vector<int> primes;
  36.  
  37. void seive() {
  38.     b.set();
  39.     b[0] = b[1] = 0;
  40.     for (int i = 2; i * i <= N; i++) {
  41.         if (b[i] == 1) {
  42.             primes.PB(i);
  43.             int k = i * i;
  44.             while (k <= N) {
  45.                 b[k] = 0;
  46.                 k += i;
  47.             }
  48.         }
  49.     }
  50. }
  51.  
  52. void segSeive(int a, int b) {
  53.     if (b < a) return;
  54.     int p[b - a + 1];
  55.     int n = b - a + 1;
  56.     for (int i = 0; i < n; i++) p[i] = 1;
  57.     for (auto i : primes) {
  58.         if (i * i > b) break;
  59.         int start = (a / i) * i;
  60.         if (i >= a and i <= b) {
  61.             start = i * 2;
  62.         }
  63.         for (int j = start; j <= b; j += i) {
  64.             p[j - a] = 0;
  65.         }
  66.     }
  67.     for (int i = 0; i < n; i++) {
  68.         if (p[i] == 1) cout << i + a << endl;
  69.     }
  70. }
  71.  
  72. int32_t main() {
  73.     __init();
  74.     seive();
  75.     int t;
  76.     cin >> t;
  77.     while (t--) {
  78.         int a, c;
  79.         cin >> a >> c;
  80.         if (a == c) {
  81.             if (b[a] == 1) cout << a;
  82.         } else if (a <= 1) {
  83.             segSeive(2, c);
  84.         } else {
  85.             segSeive(a, c);
  86.         }
  87.         cout << endl;
  88.     }
  89.     return 0;
  90. }
Success #stdin #stdout 0s 4268KB
comments (?)
stdin
copy 
2
400 1000
1 200
stdout
copy 
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
643
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
https://ideone.com/6H7wmG
language:
C++14 (gcc 8.3)
created:
3 years 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!