fork download
copy 
  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. llu Ans;
  24. vector<llu> Primes_list;
  25. vector<bool> IsPrime(1e6 + 1, true);
  26. vector<bool> Prime;
  27. void PrimeSieve(int n) {
  28.   IsPrime[0] = IsPrime[1] = false;
  29.   for (int i = 2; i * i <= n; i++)
  30.     if (IsPrime[i])
  31.       for (int j = i * i; j <= n; j += i)
  32.         IsPrime[j] = false;
  33.   for (int i = 2; i <= n; i++)
  34.     if (IsPrime[i])
  35.       Primes_list.push_back(i);
  36. }
  37.  
  38. void SegmentedPrimeSieve(llu m, llu n) {
  39.   Prime.clear();
  40.   Prime = vector<bool>(n - m + 1, true);
  41.   llu i, j;
  42.   for (i = 0; (Primes_list[i] * Primes_list[i]) <= n && i < Primes_list.size();
  43.        i++) {
  44.     if (Primes_list[i] != 0)
  45.       j = m / Primes_list[i];
  46.     j *= Primes_list[i];
  47.     for (; j <= n; j += Primes_list[i]) {
  48.       if (j < m || j == Primes_list[i])
  49.         continue;
  50.       Prime[j - m] = false;
  51.     }
  52.   }
  53.   for (i = 0; i < n - m + 1; i++)
  54.     if (Prime[i] == true)
  55.       Ans++;
  56. }
  57.  
  58. int No_Of_Factors(llu n) {
  59.   if (n == 0)
  60.     return 0;
  61.   int i, divisors = 1, power;
  62.   int N = sqrt(n);
  63.   for (i = 2; i <= N; i++) {
  64.     power = 0;
  65.     while (n % i == 0) {
  66.       power++;
  67.       n /= i;
  68.     }
  69.     divisors *= (power + 1);
  70.   }
  71.   if (n > 1)
  72.     divisors *= 2;
  73.   return divisors;
  74. }
  75. int main() {
  76.   ios_base::sync_with_stdio(false);
  77.   cin.tie(NULL);
  78.   PrimeSieve(1e6);
  79.   int t;
  80.   llu m, n;
  81.   cin >> t;
  82.   while (t--) {
  83.     Ans = 0;
  84.     cin >> m >> n;
  85.     if (m == 1)
  86.       m = 2;
  87.     llu _M = ceil(sqrt(m));
  88.     llu _N = sqrt(n);
  89.     for (llu i = _M; i <= _N; i++)
  90.       if (IsPrime[No_Of_Factors(i * i)])
  91.         Ans++;
  92.     SegmentedPrimeSieve(m, n);
  93.     cout << Ans << "\n";
  94.   }
  95.   Primes_list.clear();
  96.   IsPrime.clear();
  97.   return 0;
  98. }
Success #stdin #stdout 0s 3712KB
comments (?)
stdin
copy 
1
1 10
stdout
copy 
6
https://ideone.com/zKnCjH
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!