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

long long n, p[340000], v[340000];

void solve(){
	long long i,j,m;
    for(m=1;m*m<=n;m++){
        p[m]=n/m-1;
	}
    for(i=1;i<=m;i++){
    	v[i]=i-1;
	}
    for(i=2;i<=m;i++){
        if(v[i]==v[i-1]) continue;
        for(j=1;j<=min(m-1,n/i/i);j++){
            if(i*j<m) p[j]-=p[i*j]-v[i-1];
            else p[j]-=v[n/i/j]-v[i-1];
		}
        for(j=m;j>=i*i;j--){
            v[j]-=v[j/i]-v[i-1];
		}
    }
}

int main(){
    while(scanf("%lld",&n)!=EOF){
        solve();
        printf("%lld\n",p[1]);
    }
    return 0;
}

我们现在只知道这是一个可以求出小于n的质数的个数，并且时间复杂度在 O(n^(1/3))到 O(n^(2/3))之间，但是看不懂这是在干啥，也不知道所用的数学依据是什么，求解答。