0
已解决
新手守护
6605 酷町猫玩数学游戏
经验值：1600 时间限制：2000毫秒
题目描述 Description
给定N，求1，2,…,N中素数的个数
输入描述 Input Description
一行：一个整数N
输出描述 Output Description
一行：一个整数表示素数的个数
样例输入 Sample Input
10
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
对于40% 的数据，1≤N≤106
对于 80% 的数据，1≤N≤107
对于 100% 的数据1≤N≤108
大佬们请告诉我怎么才能不超时啊
给个思路就行!!!
王禹樊在2021-08-10 12:52:35追加了内容
0
已采纳
中级启示者
试试欧式筛
欧式筛模板
for(int i=2; i<=n; i++) {
if(!visit[i]) {
prime[++ans]=i;//是素数，放进数组
}
for(int j=1; prime[j]*i<=n&&j<=ans; j++) {
visit[i*prime[j]]=true;
if(!(i%prime[j])) break;//已经筛过了，结束
}
}
