fork download
  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
stdin
Standard input is empty
stdout
Time taken to generate = 0.079472

37607912018

Time taken = 0.600138