O(n)欧拉筛

#include<iostream>

using namespace std;

const int N = 1e7 + 10;

bool vis[N];

int prime[N], cnt;

int main(){

	int n;

	cin >> n;

	for (int i = 2; i <= n; i ++){

		if(!vis[i]){

			prime[++cnt] = i;

			vis[i] = true;  

		}

		for (int j = 1; i * prime[j] <= n && j <= cnt; j ++){

			vis[i * prime[j]] = true;

			if(i % prime[j] == 0) break;

		}

	}

	cout << cnt;

	return 0;

}

像我这样做

#include<iostream>
#include<cmath>
using namespace std;
bool prime(int n){
    for (int i=2;i<=ceil(sqrt(n));i++){
        if (n%i==0){
            return 0;
        }
    }
    return 1;
}
int main(){
    int n;
    cin>>n;
    int cnt=0;
    if (n>=2){
        cnt++;
    }
    if (n<=2000000){
        cnt=/*数量*/;
    }else if (n<=3300000){
        cnt=/*数量*/;
    }else if (n<=4300000){
       cnt=/*数量*/;
    }else if (n<=5000000){
        cnt=/*数量*/;
    }else if (n<=6000000){
        cnt=/*数量*/;
    }else if (n<=6900000){
        cnt=/*数量*/;
    }else if (n<=7700000){
        cnt=/*数量*/;
    }else if (n<=8500000){
        cnt=/*数量*/;
    }else if (n<=9250000){
        cnt=/*数量*/;
    }else{
        cnt=/*数量*/;
    }
    cout<<cnt;
    return 0;
}