欧拉筛选法求素数

#include<iostream
#include<string.h>
using namespace std;
typedef long long ll;
const ll N = 100000000; int n;
bool vis[N];
int prime[N];
int cnt= 0; //记录当前有多少个素数
void findPrime(){
memset(vis,true,sizeof(vis));
vis[0]=vis[1]=false;
for(int i = 2;i <= n;i ++){
if(vis[i]) prime[cnt++] = i; //如果未被标记为false的话，那这就是素数
for(int j = 0;j < cnt && i * prime[j] <= n;j ++){
vis[i * prime[j]] = false; //该素数的倍数肯定不是素数
if(i % prime[j] == 0) break;
/当i是prime[j]的整数倍时，记 m = i / prime[j]，那么 i * prime[j+1] 就可以变为 (m * prime[j+1]) * prime[j]，而mprime[j+1]>i，
这说明 i * prime[j+1] 是 prime[j] 的整数倍，不需要再进行标记(在之后会被 prime[j] * 某个数（mprime[j+1]） 标记)，
对于 prime[j+2] 及之后的素数同理，直接跳出循环，这样就避免了重复标记。/
}
}
}
int main(){
cin>>n;
findPrime();
for(int i=0;i<cnt;i++)
cout<<prime[i]<<" ";
return 0;
}

欧拉筛选法的关键在于筛选时对合数只标记一次，注释中有详解，看注释吧。QAQ