欧拉筛AC

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e7+10;
const int INF=0x3f3f3f3f;
int p[N],n,cnt;
bool f[N];
int main()
{
	IOS;
	cin>>n;
	for(int i=2;i<=n;++i)
	{
		if(!f[i])
		{
			p[++cnt]=i;
		}
		for(int j=1;j<=cnt && i*p[j]<=n;++j)
		{
			f[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	} 
	cout<<cnt;
    return 0;
}

初学者勿做，要用筛法

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e7;
bool is[maxn+10];
int sum,n;
int main(){
 cin>>n;
    memset(is,0,sizeof is);
    is[1]=1;
    for(int i=2;i<=maxn;i++){
        for(int j=2;i*j<=maxn;j++){
            is[i*j]=1;
        }
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        if(is[i]==0)
            sum++;
    }
    cout<<sum;
    return 0;
}