fork download
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. ll count_primes(ll n) {
  7. vector<ll> v;
  8. for (ll k = 1; k * k <= n; ++k) {
  9. v.push_back(n / k);
  10. v.push_back(k);
  11. }
  12. sort(v.begin(), v.end());
  13. v.erase(unique(v.begin(), v.end()), v.end());
  14.  
  15. // return i such that v[i] = x
  16. // since v[i] = i + 1 for i <= sqrt(n) and v[v.size() - i] = n / i for i <= sqrt(n),
  17. // we can calculate index in O(1)
  18. ll sq = sqrt(n);
  19. auto geti = [&](ll x) {
  20. if (x <= sq) return (int)x - 1;
  21. else return (int)(v.size() - (n / x));
  22. };
  23.  
  24. vector<ll> dp(v.size());
  25.  
  26. // S(n, 0) = n
  27. for (int i = 0; i < v.size(); ++i)
  28. dp[i] = v[i];
  29.  
  30. int a = 0;
  31. for (ll p = 2; p * p <= n; ++p) {
  32. // this condition is true for primes
  33. if (dp[geti(p)] != dp[geti(p - 1)]) {
  34. ++a;
  35. for (int i = (int)v.size() - 1; i >= 0; --i) {
  36. if (v[i] < p * p) break;
  37. dp[i] -= dp[geti(v[i] / p)] - a;
  38. }
  39. }
  40. }
  41.  
  42. return dp[geti(n)] - 1;
  43. }
  44.  
  45. int main() {
  46. ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  47.  
  48. vector<ll> ns = {(ll)1e10, (ll)1e11, (ll)1e12, (ll)1e13};
  49. for (ll n : ns) {
  50. auto start_time = clock();
  51. cout << "n = " << (double)n << endl;
  52. ll res = count_primes(n);
  53. cout << "result: " << res << endl;
  54. cout << "time: " << (double)(clock() - start_time) / CLOCKS_PER_SEC << "s" << endl;
  55. cout << endl;
  56. }
  57.  
  58. return 0;
  59. }
  60.  
Time limit exceeded #stdin #stdout 15s 103108KB
stdin
Standard input is empty
stdout
n = 1e+10
result: 455052511
time: 0.146883s

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

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

n = 1e+13