http://poj.openjudge.cn/practice/C26E/

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using u64 = unsigned long long;
using u128 = __uint128_t;

const ll INF = (ll)4e18;

const int SIEVE_MAX = 5000000;
const int PHI_X = 100000;
const int PHI_A = 100;

vector<int> primes;
vector<int> pi_pref;
vector<unsigned char> comp;

static int phi_tbl[PHI_A + 1][PHI_X + 1];

void sieve() {
    comp.assign(SIEVE_MAX + 1, 0);
    pi_pref.assign(SIEVE_MAX + 1, 0);

    for (int i = 2; i <= SIEVE_MAX; ++i) {
        if (!comp[i]) primes.push_back(i);

        for (int p : primes) {
            long long v = 1LL * i * p;
            if (v > SIEVE_MAX) break;

            comp[(int)v] = 1;
            if (i % p == 0) break;
        }
    }

    int cnt = 0;
    for (int i = 0; i <= SIEVE_MAX; ++i) {
        if (i >= 2 && !comp[i]) ++cnt;
        pi_pref[i] = cnt;
    }
}

void init_phi_table() {
    for (int x = 0; x <= PHI_X; ++x) phi_tbl[0][x] = x;

    for (int a = 1; a <= PHI_A; ++a) {
        int p = primes[a - 1];
        for (int x = 0; x <= PHI_X; ++x) {
            phi_tbl[a][x] = phi_tbl[a - 1][x] - phi_tbl[a - 1][x / p];
        }
    }
}

ll isqrt_ll(ll x) {
    ll r = sqrt((long double)x);
    while ((r + 1) <= x / (r + 1)) ++r;
    while (r > x / r) --r;
    return r;
}

ll icbrt_ll(ll x) {
    ll r = cbrt((long double)x);
    while ((u128)(r + 1) * (r + 1) * (r + 1) <= (u64)x) ++r;
    while ((u128)r * r * r > (u64)x) --r;
    return r;
}

ll i4rt_ll(ll x) {
    ll r = sqrt(sqrt((long double)x));

    auto fourth = [](ll v) -> u128 {
        return (u128)v * v * v * v;
    };

    while (fourth(r + 1) <= (u64)x) ++r;
    while (fourth(r) > (u64)x) --r;
    return r;
}

ll prime_pi(ll x);

ll phi_count(ll x, int a) {
    if (x == 0) return 0;
    if (a == 0) return x;

    if (a <= PHI_A && x <= PHI_X) {
        return phi_tbl[a][(int)x];
    }

    if (a - 1 < (int)primes.size() && primes[a - 1] >= x) {
        return 1;
    }

    if (a < (int)primes.size() && 1LL * primes[a] * primes[a] > x) {
        return prime_pi(x) - a + 1;
    }

    ll res = x;
    for (int i = 0; i < a; ++i) {
        res -= phi_count(x / primes[i], i);
    }

    return res;
}

unordered_map<ll, ll> pi_cache;

ll prime_pi(ll x) {
    if (x <= SIEVE_MAX) return pi_pref[(int)x];

    auto it = pi_cache.find(x);
    if (it != pi_cache.end()) return it->second;

    ll a = prime_pi(i4rt_ll(x));
    ll b = prime_pi(isqrt_ll(x));
    ll c = prime_pi(icbrt_ll(x));

    ll sum = phi_count(x, (int)a) + (b + a - 2) * (b - a + 1) / 2;

    for (ll i = a; i < b; ++i) {
        ll w = x / primes[(size_t)i];

        sum -= prime_pi(w);

        if (i < c) {
            ll lim = prime_pi(isqrt_ll(w));
            for (ll j = i; j < lim; ++j) {
                sum -= prime_pi(w / primes[(size_t)j]) - j;
            }
        }
    }

    pi_cache[x] = sum;
    return sum;
}

ll mod_pow(ll a, ll d, ll mod) {
    u128 res = 1;
    u128 base = (u64)a % (u64)mod;

    while (d) {
        if (d & 1) res = res * base % (u64)mod;
        base = base * base % (u64)mod;
        d >>= 1;
    }

    return (ll)res;
}

bool is_prime64(ll n) {
    if (n < 2) return false;

    for (ll p : {2LL, 3LL, 5LL, 7LL, 11LL, 13LL, 17LL, 19LL, 23LL, 29LL, 31LL, 37LL}) {
        if (n % p == 0) return n == p;
    }

    ll d = n - 1;
    ll s = 0;

    while ((d & 1) == 0) {
        d >>= 1;
        ++s;
    }

    for (ll a : {2LL, 3LL, 5LL, 7LL, 11LL, 13LL, 17LL, 19LL, 23LL, 29LL, 31LL, 37LL}) {
        if (a >= n) continue;

        ll x = mod_pow(a, d, n);
        if (x == 1 || x == n - 1) continue;

        bool composite = true;

        for (int r = 1; r < s; ++r) {
            x = (ll)((u128)x * x % (u64)n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }

        if (composite) return false;
    }

    return true;
}

ll next_prime_gt_half(ll x) {
    ll v = x / 2 + 1;

    if (v <= 2) return 2;
    if ((v & 1) == 0) ++v;

    while (!is_prime64(v)) v += 2;

    return v;
}

unordered_map<ll, ll> g_cache;

ll get_g(ll x) {
    if (x == 1) return INF;

    auto it = g_cache.find(x);
    if (it != g_cache.end()) return it->second;

    for (int p : primes) {
        if (1LL * p * p > x) break;

        if ((ll)p < get_g(x / p)) {
            g_cache[x] = p;
            return p;
        }
    }

    ll ret = next_prime_gt_half(x);
    g_cache[x] = ret;
    return ret;
}

ll count_spf_less(ll m, ll t) {
    if (m <= 1 || t <= 2) return 0;

    if (t >= INF / 2 || t > m) {
        return m - 1;
    }

    int a;

    if (t - 1 <= SIEVE_MAX) {
        a = pi_pref[(int)(t - 1)];
    } else {
        a = (int)prime_pi(t - 1);
    }

    return m - phi_count(m, a);
}

ll solve(ll n) {
    if (n == 1) return 1;

    g_cache.clear();
    g_cache.reserve(1 << 20);

    ll ans = 0;

    for (ll l = 1; l <= n; ) {
        ll x = n / l;
        ll r = n / x;

        ll t = get_g(x);

        ans += count_spf_less(r, t) - count_spf_less(l - 1, t);

        l = r + 1;
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    sieve();
    init_phi_table();

    pi_cache.reserve(1 << 16);

    ll n;
    cin >> n;

    cout << solve(n) << '\n';

    return 0;
}