fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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
https://ideone.com/Pn0mi9
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!