fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. bool P[1000007];
  6. vector<ll> segmentedSieve(ll L, ll R){
  7.     vector<ll> primesInRange;
  8.  
  9.     for (ll i = 0; i <= R - L + 1; i++)
  10.         P[i] = 1;
  11.  
  12.     for (ll i = 2; i <= sqrt(R); i++)
  13.         for (ll j = max(i * i, (L + i - 1) / i * i); j <= R; j += i)
  14.             P[j - L] = 0;
  15.  
  16.     for (ll i = L; i <= R; i++)
  17.         if (P[i - L])
  18.             primesInRange.push_back(i);
  19.  
  20.     return primesInRange;
  21. }
  22.  
  23. int main(){
  24.     int t;
  25.     cin >> t;
  26.     while (t--){
  27.         ll L, R;
  28.         cin >> L >> R;
  29.         int dem = 0;
  30.         for (ll x : segmentedSieve(L, R))
  31.             cout << x << "\n";
  32.     }
  33.     return 0;
  34. }
Success #stdin #stdout 0s 5264KB
comments (?)
stdin
copy 
2
2 10
2801 2810
stdout
copy 
2
3
5
7
2801
2803
https://ideone.com/ZSPB15
language:
C++14 (gcc 8.3)
created:
1 day 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!