fork(5) download
copy 
  1. #include <bits/stdtr1c++.h>
  2.  
  3. #define MAXN 100
  4. #define MAXM 100010
  5. #define MAXP 10000010
  6.  
  7. using namespace std;
  8.  
  9. int prime_cnt[MAXP];
  10. long long dp[MAXN][MAXM];
  11.  
  12. vector<int> primes;
  13. bitset<MAXP> is_prime;
  14.  
  15. void sieve(){
  16.     is_prime[2] = true;
  17.     for (int i = 3; i < MAXP; i += 2) is_prime[i] = true;
  18.  
  19.     for (int i = 3; i * i < MAXP; i += 2){
  20.         for (int j = i * i; is_prime[i] && j < MAXP; j += (i << 1)){
  21.             is_prime[j] = false;
  22.         }
  23.     }
  24.  
  25.     for (int i = 1; i < MAXP; i++){
  26.         prime_cnt[i] = prime_cnt[i - 1] + is_prime[i];
  27.         if (is_prime[i]) primes.push_back(i);
  28.     }
  29. }
  30.  
  31. void gen(){
  32.     sieve();
  33.  
  34.     for (int m = 0; m < MAXM; m++) dp[0][m] = m;
  35.     for (int n = 1; n < MAXN; n++){
  36.         for (int m = 0; m < MAXM; m++){
  37.             dp[n][m] = dp[n - 1][m] - dp[n - 1][m / primes[n - 1]];
  38.         }
  39.     }
  40. }
  41.  
  42. long long phi(long long m, int n){
  43.     if (n == 0) return m;
  44.     if (m < MAXM && n < MAXN) return dp[n][m];
  45.     if ((long long)primes[n - 1] * primes[n - 1] >= m && m < MAXP) return prime_cnt[m] - n + 1;
  46.  
  47.     return phi(m, n - 1) - phi(m / primes[n - 1], n - 1);
  48. }
  49.  
  50. long long lehmer(long long m){
  51.     if (m < MAXP) return prime_cnt[m];
  52.  
  53.     int s = sqrt(0.5 + m), y = cbrt(0.5 + m);
  54.     int a = prime_cnt[y];
  55.  
  56.     long long res = phi(m, a) + a - 1;
  57.     for (int i = a; primes[i] <= s; i++){
  58.         res = res - lehmer(m / primes[i]) + lehmer(primes[i]) - 1;
  59.     }
  60.     return res;
  61. }
  62.  
  63. int main(){
  64.     auto start = clock();
  65.     gen();
  66.     printf("Time taken to generate = %0.6f\n\n", (clock() - start) / (double)CLOCKS_PER_SEC);
  67.  
  68.     cout << lehmer(1e12) << endl;
  69.     printf("\nTime taken = %0.6f\n", (clock() - start) / (double)CLOCKS_PER_SEC);
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.61s 125096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Time taken to generate = 0.079472

37607912018

Time taken = 0.600138
https://ideone.com/SnhEQA
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!