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

using ll=long long;
const int N = 4e5+5;
int id1[N],id2[N];

int p[N],tot;
bool vis[N];
void init(){ // 筛出前 sqrt(n) 的质数
    for(int i=2;i<N;i++){
        if(!vis[i]){
            p[++tot] = i;
        }

        for(int j=1;j<=tot && p[j]*i<N;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
};

ll v[N*2], g[N*2];
int main(){
    ll n; cin>>n;
    int m=0;

    init();
    for(ll l=1,r;l<=n;l=r+1){ // 数论分块
        r = n/(n/l); 
        v[++m] = n/l; 
        if(v[m]<N)id1[v[m]]=m;
        else id2[n/v[m]]=m;

        g[m] = v[m]-1;
    }
    
    auto get = [&](ll x){
        return x<N?id1[x]:id2[n/x];
    };

    for(int j=1;j<=tot;j++){ // 递推求出所有的 g
        for(int i=1;i<=m&&p[j]<=v[i]/p[j];i++){
            g[i] -= g[get(v[i]/p[j])] - g[get(p[j-1])];
        }
    }

    cout << g[get(n)] << '\n';
    return 0;
}

练习：https://qoj.ac/contest/1871/problem/9867。