fork(1) 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
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