fork(1) download 
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cctype>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <map>
  10. #include <numeric>
  11. #include <set>
  12. #include <vector>
  13.  
  14. #define lld long long
  15. #define llu unsigned long long
  16.  
  17. #define rep(i, x, y) for (i = x; i < y; i++)
  18. #define rrep(i, x, y) for (i = x; i >= y; i--)
  19. #define trv(y, x) for (typeof(x.begin()) y = x.begin(); y != x.end(); y++)
  20.  
  21. using namespace std;
  22.  
  23. vector<int> Primes_list;
  24. vector<bool> Prime;
  25. void PrimeSieve(int n) {
  26.   vector<bool> IsPrime(n + 1, true);
  27.   IsPrime[0] = IsPrime[1] = false;
  28.   for (int i = 2; i * i <= n; i++)
  29.     if (IsPrime[i])
  30.       for (int j = i * i; j <= n; j += i)
  31.         IsPrime[j] = false;
  32.   for (int i = 2; i <= n; i++)
  33.     if (IsPrime[i])
  34.       Primes_list.push_back(i);
  35. }
  36.  
  37. void SegmentedPrimeSieve(int m, int n) {
  38.   Prime.clear();
  39.   Prime = vector<bool>(n - m + 1, true);
  40.   int i, j;
  41.   for (i = 0; (Primes_list[i] * Primes_list[i]) <= n && i < Primes_list.size();
  42.        i++) {
  43.     if (Primes_list[i] != 0)
  44.       j = m / Primes_list[i];
  45.     j *= Primes_list[i];
  46.     for (; j <= n; j += Primes_list[i]) {
  47.       if (j < m || j == Primes_list[i])
  48.         continue;
  49.       Prime[j - m] = false;
  50.     }
  51.   }
  52.   for (i = 0; i < n - m + 1; i++)
  53.     if (Prime[i] == true)
  54.       cout << i + m << "\n";
  55. }
  56.  
  57. int main() {
  58.   ios_base::sync_with_stdio(false);
  59.   cin.tie(NULL);
  60.   PrimeSieve(ceil(sqrt(1e9)));
  61.   int t, m, n;
  62.   cin >> t;
  63.   while (t--) {
  64.     cin >> m >> n;
  65.     if (m == 1)
  66.       m = 2;
  67.     SegmentedPrimeSieve(m, n);
  68.     cout << "\n";
  69.   }
  70.   Primes_list.clear();
  71.   return 0;
  72. }
Success #stdin #stdout 0s 3588KB
comments (?)
stdin 
2
1 10
3 5
stdout 
2
3
5
7

3
5
https://ideone.com/Jj7Vui
language:
C++ (gcc 8.3)
created:
8 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!