fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define size 10000010
  6.  
  7. bool sieve[size + 1];
  8. bool segsieve[size + 1];
  9. int main()
  10. {
  11.  
  12.     ios::sync_with_stdio(0);
  13.     cin.tie(0);
  14. #ifndef ONLINE_JUDGE
  15.     freopen("input.txt", "r", stdin);
  16.     freopen("output.txt", "w", stdout);
  17. #endif
  18.  
  19.  
  20.     for (ll i = 0; i <= size; i++)
  21.         sieve[i] = true;
  22.     sieve[0] = false;
  23.     sieve[1] = false;
  24.     for (ll i = 2; i <= size; i++)
  25.     {
  26.         if (sieve[i])
  27.         {
  28.             for (ll j = i * i; j <= size; j += i)
  29.                 sieve[j] = false;
  30.         }
  31.     }
  32.  
  33.     ll t;
  34.     cin >> t;
  35.     while (t--)
  36.     {
  37.  
  38.         ll a, b;
  39.         cin >> a;
  40.         cin >> b;
  41.         for (ll i = 0; i <= b - a; i++)
  42.             segsieve[i] = true;
  43.  
  44.         if (a == 1)
  45.             segsieve[0] = false;
  46.  
  47.         for (ll i = 2; i <= sqrt(b); i++)
  48.         {
  49.             if (sieve[i])
  50.             {
  51.                 ll j = a;
  52.                 while (j % i != 0)
  53.                     j++;
  54.                 while (j <= b)
  55.                 {
  56.                     segsieve[j - a] = false;
  57.                     j += i;
  58.                 }
  59.             }
  60.         }
  61.  
  62.         for (ll i = a; i <= b; i++)
  63.         {
  64.             if (segsieve[i - a])
  65.                 cout << i << endl;
  66.         }
  67.         if (t)
  68.             cout << endl;
  69.  
  70.     }
  71.  
  72.  
  73.  
  74.     return 0;
  75. }
Success #stdin #stdout 0.07s 13224KB
comments (?)
stdin 
3
5 10
11 20
7 15
stdout 
5
7

11
13
17
19

7
11
13
https://ideone.com/Ewgr4G
language:
C++14 (gcc 8.3)
created:
6 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!