#include <bits/stdtr1c++.h>

#define MAXN 100
#define MAXM 100010
#define MAXP 10000010

using namespace std;

int prime_cnt[MAXP];
long long dp[MAXN][MAXM];

vector<int> primes;
bitset<MAXP> is_prime;

void sieve(){
    is_prime[2] = true;
    for (int i = 3; i < MAXP; i += 2) is_prime[i] = true;

    for (int i = 3; i * i < MAXP; i += 2){
        for (int j = i * i; is_prime[i] && j < MAXP; j += (i << 1)){
            is_prime[j] = false;
        }
    }

    for (int i = 1; i < MAXP; i++){
        prime_cnt[i] = prime_cnt[i - 1] + is_prime[i];
        if (is_prime[i]) primes.push_back(i);
    }
}

void gen(){
    sieve();

    for (int m = 0; m < MAXM; m++) dp[0][m] = m;
    for (int n = 1; n < MAXN; n++){
        for (int m = 0; m < MAXM; m++){
            dp[n][m] = dp[n - 1][m] - dp[n - 1][m / primes[n - 1]];
        }
    }
}

long long phi(long long m, int n){
    if (n == 0) return m;
    if (m < MAXM && n < MAXN) return dp[n][m];
    if ((long long)primes[n - 1] * primes[n - 1] >= m && m < MAXP) return prime_cnt[m] - n + 1;

    return phi(m, n - 1) - phi(m / primes[n - 1], n - 1);
}

long long lehmer(long long m){
    if (m < MAXP) return prime_cnt[m];

    int s = sqrt(0.5 + m), y = cbrt(0.5 + m);
    int a = prime_cnt[y];

    long long res = phi(m, a) + a - 1;
    for (int i = a; primes[i] <= s; i++){
        res = res - lehmer(m / primes[i]) + lehmer(primes[i]) - 1;
    }
    return res;
}

int main(){
    auto start = clock();
    gen();
    printf("Time taken to generate = %0.6f\n\n", (clock() - start) / (double)CLOCKS_PER_SEC);

    cout << lehmer(1e12) << endl;
    printf("\nTime taken = %0.6f\n", (clock() - start) / (double)CLOCKS_PER_SEC);

    return 0;
}