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;

}