fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void simpleSieve(int lmt, vector<int>& prime) {
  4.    bool mark[lmt + 1];
  5.    memset(mark, false, sizeof(mark));
  6.    for (int i = 2; i <= lmt; ++i) {
  7.       if (mark[i] == false) {
  8.          prime.push_back(i);
  9.          for (int j = i; j <= lmt; j += i)
  10.             mark[j] = true;
  11.       }
  12.    }
  13. }
  14. void PrimeInRange(int low, int high) {
  15.    int lmt = floor(sqrt(high)) + 1;
  16.    vector<int> prime;
  17.    simpleSieve(lmt, prime);
  18.    int n = high - low + 1;
  19.    bool mark[n + 1];
  20.    memset(mark, false, sizeof(mark));
  21.    for (int i = 0; i < prime.size(); i++) {
  22.       int lowLim = floor(low / prime[i]) * prime[i];
  23.       if (lowLim < low)
  24.          lowLim += prime[i];
  25.       for (int j = lowLim; j <= high; j += prime[i])
  26.          mark[j - low] = true;
  27.    }
  28.    for (int i = low; i <= high; i++)
  29.       if (!mark[i - low])
  30.          cout << i << "\n";
  31. }
  32. int main() {
  33.    int t;cin>>t;
  34.    while(t--){
  35.    int m,n;cin>>m>>n;
  36. 	PrimeInRange(m,n);
  37.    }
  38. }
  39.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
2
1 10
3 5
stdout
copy 
1
5
7
5
https://ideone.com/YPuFye
language:
C++14 (gcc 8.3)
created:
7 days 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!