暴力出奇迹

粗略推算一下，一个数只有第 $6$ 取余为 $1$ 或 $5$ 才有可能是质数.
通过这个办法，我们可以将数据范围从 $10^6$ 降至 $3.3\times 10^5$.
最后配上 $O(n\sqrt n)$ 的判断就行了

#include <iostream>
#include <cstdio>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
inline bool check(int n){
	if(n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return 0;
	for(int i = 6; i * i <= n; i += 6){
		if(n % (i + 1) == 0) return 0;
		if(n % (i + 5) == 0) return 0;
	}
	return 1;
}
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int n;
	cin >> n;
	if(n < 2){
		cout << 0;
		return 0;
	}
	int ct = 1;
	if(n >= 3) ct++;
	if(n >= 5) ct++;
	for(int i = 6; i <= n; i += 6){
		if(n >= i + 1) ct += check(i + 1);
		if(n >= i + 5) ct += check(i + 5);
	}
	cout << ct;

	return 0;
}