- 2022tysc0158 的博客
【模板】素数筛
- 2024-4-6 9:31:22 @
#include<cstdio>
int n,prime[1000001],tot;
bool mark[1000001];
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++){
if(!mark[i])prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<=n;j++){
mark[prime[j]*i]=true;
if(i%prime[j]==0)break;
}
}
}