题解

标准欧拉筛

#include<bits/stdc++.h>
using namespace std;
long long f[100001],p[100001],cnt=0,n;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin>>n;
    f[1]=1;
    for(int i=2;i<=n;i++){
        if(f[i]==0){
            p[++cnt]=i;
        }
        for(int j=1;p[j]*i<=n&&j<=cnt;j++){
            f[p[j]*i]=1;
            if(i%p[j]==0) break;
        }
    }
    cout<<cnt+1;//将1也计算在内
	return 0;
}

欢迎大佬提出修改意见