素数生成: エラトステネスの篩

こんにちは。Arkです。
たまに素数の生成が必要な時があるので、備忘録のために素数の生成方法について書きたいと思います。

まず、最も自然な素数の生成法を書きます。（読み飛ばしてもらっても構いません）
最も小さい素数である2を素数の欄に入れます。次に2より大きい数字を順にみていき素数の欄に入っている数字で割ってみます。素数の欄に入っている数字で割ってみて、どれで割っても余りが1以上であればその数字は素数です。よってその数を素数の欄に入れます。これを繰り返すと素数が生成されます。
しかし、これは計算量が膨大になり実行時間が莫大にかかります。そこで、偉い人が考えたのが"エラトステネスの篩"です。

• エラトステネスの篩

詳しくはソースコードを読んでもらった方が分かりやすいと思うので以下をご覧ください。

bool a[1000001];
int n=1000000;
vector<int> v;

void Eratosthenes(int N){
	for(int i=0;i<N;i++)
		a[i]=true;
	for(int i=2;i<sqrt(N);i++){
		if(a[i]){
			for(int j=0;i*(j+2)<N;j++)
				a[i*(j+2)]=false;
		}
	}
	for(int i=2;i<N;i++)
		if(a[i])
			v.push_back(i);
	//for(auto z:v)cout<<z<<" ";
}

int main(){
	Eratosthenes(n);
}

軽く説明します。
まず小さい数字を全て素数と仮定します。その後に小さい数字から見ていき、その数の倍数である数を全て消去します（素数の候補から外します）。
これを繰り返すことで素数を高速で求めることが出来ます。ちなみにこのソースコードでいうvが素数の集まりで、コメント文を実行してもらえればすべての素数が列挙されます。

今回はN=1000000で行いました。実行時間はだいたい0.15秒です。非常に高速ですね！！！