fork(6) download 
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. struct _count_primes_struct_t_ {
  7.     vector<int> primes;
  8.     vector<int> mnprimes;
  9.     ll ans;
  10.     ll y;
  11.     vector<pair<pair<ll, int>, char>> queries;
  12.  
  13.     ll count_primes(ll n) {
  14.         // this y is actually n/y
  15.         // also no logarithms, welcome to reality, this y is the best for n=10^12 or n=10^13
  16.         y = pow(n, 0.64);
  17.         if (n < 100) y = n;
  18.  
  19.         // linear sieve
  20.         primes.clear();
  21.         mnprimes.assign(y + 1, -1);
  22.         ans = 0;
  23.         for (int i = 2; i <= y; ++i) {
  24.             if (mnprimes[i] == -1) {
  25.                 mnprimes[i] = primes.size();
  26.                 primes.push_back(i);
  27.             }
  28.             for (int k = 0; k < primes.size(); ++k) {
  29.                 int j = primes[k];
  30.                 if (i * j > y) break;
  31.                 mnprimes[i * j] = k;
  32.                 if (i % j == 0) break;
  33.             }
  34.         }
  35.         if (n < 100) return primes.size();
  36.         ll s = n / y;
  37.  
  38.         for (int p : primes) {
  39.             if (p > s) break;
  40.             ans++;
  41.         }
  42.         // pi(n / y)
  43.         int ssz = ans;
  44.  
  45.         // F with two pointers
  46.         int ptr = primes.size() - 1;
  47.         for (int i = ssz; i < primes.size(); ++i) {
  48.             while (ptr >= i && (ll)primes[i] * primes[ptr] > n)
  49.                 --ptr;
  50.             if (ptr < i) break;
  51.             ans -= ptr - i + 1;
  52.         }
  53.  
  54.         // phi, store all queries 
  55.         phi(n, ssz - 1);
  56.  
  57.         sort(queries.begin(), queries.end());
  58.         int ind = 2;
  59.         int sz = primes.size();
  60.  
  61.         // the order in fenwick will be reversed, because prefix sum in a fenwick is just one query
  62.         fenwick fw(sz);
  63.         for (auto [na, sign] : queries) {
  64.             auto [n, a] = na;
  65.             while (ind <= n)
  66.                 fw.add(sz - 1 - mnprimes[ind++], 1);
  67.             ans += (fw.ask(sz - a - 2) + 1) * sign;
  68.         }
  69.         queries.clear();
  70.         return ans - 1;
  71.     }
  72.  
  73.     void phi(ll n, int a, int sign = 1) {
  74.         if (n == 0) return;
  75.         if (a == -1) {
  76.             ans += n * sign;
  77.             return;
  78.         }
  79.         if (n <= y) {
  80.             queries.emplace_back(make_pair(n, a), sign);
  81.             return;
  82.         }
  83.         phi(n, a - 1, sign);
  84.         phi(n / primes[a], a - 1, -sign);
  85.     }
  86.  
  87.     struct fenwick {
  88.         vector<int> tree;
  89.         int n;
  90.  
  91.         fenwick(int n = 0) : n(n) {
  92.             tree.assign(n, 0);
  93.         }
  94.  
  95.         void add(int i, int k) {
  96.             for (; i < n; i = (i | (i + 1)))
  97.                 tree[i] += k;
  98.         }
  99.  
  100.         int ask(int r) {
  101.             int res = 0;
  102.             for (; r >= 0; r = (r & (r + 1)) - 1)
  103.                 res += tree[r];
  104.             return res;
  105.         }
  106.     };
  107. } _count_primes_struct_;
  108.  
  109. int main() {
  110.     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  111.  
  112.     vector<ll> ns = {(ll)1e10, (ll)1e11, (ll)1e12, (ll)1e13};
  113.     for (ll n : ns) {
  114.         auto start_time = clock();
  115.         cout << "n = " << (double)n << endl;
  116.         ll res = _count_primes_struct_t_().count_primes(n);
  117.         cout << "result: " << res << endl;
  118.         cout << "time: " << (double)(clock() - start_time) / CLOCKS_PER_SEC << "s" << endl;
  119.         cout << endl;
  120.     }
  121.  
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 5.54s 1260568KB
comments (?)
stdin 
Standard input is empty
stdout 
n = 1e+10
result: 455052511
time: 0.044909s

n = 1e+11
result: 4118054813
time: 0.200109s

n = 1e+12
result: 37607912018
time: 0.913579s

n = 1e+13
result: 346065536839
time: 4.37183s
https://ideone.com/aYqdcM
language:
C++14 (gcc 8.3)
created:
3 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!