fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ull unsigned long long
  3. #define ll long long
  4. #define all(x) x.begin(), x.end()
  5. using namespace std;
  6. const int maxn = 1e6 + 1;
  7. int D[maxn], prime[maxn], pre[maxn];
  8. void Sieve() {
  9.     D[0] = 0; D[1] = 1;
  10.     for (int i = 2; i <= sqrt(maxn); ++i) {
  11.         for (int j = 2; j <= maxn / i; ++j) {
  12.             D[i * j]++;
  13.         }
  14.     }
  15.     for (int i = 2; i <= maxn; ++i) D[i] += 2;
  16. }
  17. void SangNT() {
  18.     prime[0] = prime[1] = 1;
  19.     for (int i = 2; i <= sqrt(maxn); ++i) {
  20.         if (prime[i] == 0) {
  21.             for (int j = i; j <= maxn / i; ++j) {
  22.                 prime[i * j] = 1;
  23.             }
  24.         }
  25.     }
  26. }
  27. int main() {
  28.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  29.     SangNT();
  30.     Sieve();
  31.     for (int i = 1; i <= maxn; ++i) {
  32.         if (prime[D[i]] == 0) {
  33.             pre[i] = pre[i - 1] + 1;
  34.         }
  35.         else pre[i] = pre[i - 1];
  36.     }
  37.  
  38.     int q, l, r;
  39.     cin >> q;
  40.     while (q--) {
  41.         cin >> l >> r;
  42.         cout << pre[r] - pre[l - 1] << endl;
  43.     }
  44.  
  45. }
  46.  
  47.  
Success #stdin #stdout 0.03s 15328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ciwSrR
Bài 4 _ Thầy Kiều :Đ
language:
C++14 (gcc 8.3)
created:
11 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!