C++における2種類の質量ふるい法

1つ目:Eratosthenesふるい法O(N log log N)
このふるい法の核心は2~Nの間の数を列挙して、彼らの倍数をすべて質数ではありませんとして、もしふるいが1つの質数ではありませんまで直接スキップすればよくて、またx^2より小さいxの倍数はすべてxより小さい数にすでにマークされたので、直接x^2から始めることができます

inline void primes(int n) {
	for(re i=2;i<=n;i++) {
		if(v[i]) continue;
		for(re j=i;j<=n/i;j++) v[i*j]=1;
	}
}

1つの数が素数かどうかを判断し、0であれば素数であり、特判1は素数ではないことに注意する
第二種類:線形ふるい法O(N)

inline void primes(int n) {
	memset(v,0,sizeof(v)); m=0;
	for(re i=2;i<=n;i++) {
		if(!v[i]) { v[i]=i; prime[++m]=i; }
		for(re j=1;j<=m;j++) {
			if(prime[j]>v[i]||prime[j]>n/i) break;
			v[i*prime[j]]=prime[j];
		}
	}
}