C++で素数を求めよう（エラトステネスの篩）

皆さんこんにちは
お元気ですか。さて、本日は素数を求めてみます。

素数とかいう不思議な値がこの世には有ります。

普段の生活において何に使うのかよくわかりませんが、プログラミングのコンテストとかで素数を利用した解き方もあるようです。

素数の特徴

計算する上で大事な情報はひとつ
自分自身と１しかない。＝約数が２つ
（Ex.7 = 1,7）

プログラム

普通の解き方

要は約数の数が２つであれば、素数なんだと…
つまり、約数の数を数えて２つの数のみ出力すればいいわけです。
プログラム上ではこのように書けます。

void normal(){
	for(int i = 1; i <= N; i++){
		int count = 0;
		for(int j = 1; j <= i; j++){
			if(i % j == 0){
				count++;
			}
			if(count > 2){
				break;
			}
		}
		if(count == 2){
			//cout << i << endl;
		}
	}
}

エラトステネスの篩

世の中にはこのような素数を高速に検出する手法が提案されています。

１，リストに２〜Nまでの値を入れる
２，探索リストの倍数をふるい落とす。（素数ではないとする）
３，sqrt(N)まで繰り返す
４，Trueのものを繰り返す。

void Eratosthenes(){
	for(int i = 0; i < N; i++){
		arr[i] = 1;
	}
	for(int i = 2; i < sqrt(N); i++){
		if(arr[i]){
			for(int j = 0; i * (j + 2) < N; j++){
				arr[i *(j + 2)] = 0;
			}
		}
	}

	for(int i = 2; i < N; i++){
		if(arr[i]){
			//cout << i << endl;
		}
	}
}

速度計測

最後に速度を求めてみました。
N=1000000で。

普通：238.615
エラトステネスの篩：0.02558

すごく、、早いです。

参考文献

エラトステネスの篩 - Wikipedia

ソースコード

#include <iostream>
#include <math.h>

#define N 1000000
using namespace std;

int arr[N];

//エラトステネスの篩
void Eratosthenes(){
	for(int i = 0; i < N; i++){
		arr[i] = 1;
	}
	for(int i = 2; i < sqrt(N); i++){
		if(arr[i]){
			for(int j = 0; i * (j + 2) < N; j++){
				arr[i *(j + 2)] = 0;
			}
		}
	}

	for(int i = 2; i < N; i++){
		if(arr[i]){
			//cout << i << endl;
		}
	}
}

void normal(){
	for(int i = 1; i <= N; i++){
		int count = 0;
		for(int j = 1; j <= i; j++){
			if(i % j == 0){
				count++;
			}
			if(count > 2){
				break;
			}
		}
		if(count == 2){
			//cout << i << endl;
		}
	}
}

//素数
int main(int argc, char const *argv[]){
	clock_t start = clock();
	normal();
	clock_t end = clock();
	cout << (double)(end - start) / CLOCKS_PER_SEC << endl;
	cout << "エラトステネスの篩	" << endl;
	start = clock();
	Eratosthenes();
	end = clock();
	cout << (double)(end - start) / CLOCKS_PER_SEC << endl;
	return 0;
}