Eratosthenes の篩

前回のエントリの続きでまた素数の話．
Team-lablog » 1000万個目の素数を超高速に出力せよ
これに触発されて 1 000 万番目までの素数の出力とその高速化に挑戦してみる．
まずは前回のソースコードをちょっと手直しして，

#include <iostream>
#include <ctime> //実行時間の測定
using namespace std;
#define MAX 180000000

int main(){
	int count = 0;
	clock_t begin, finish;
	begin = clock();
	bool *num;
	num = new bool[MAX];
	for(int i = 0; i < MAX; i++){
		num[i] = true;
	}

	num[0] = false;
	num[1] = false;
	
	for(int i = 2; i * i <= MAX; i++){
		for(int j = i * 2; j <= MAX; j += i){
			if(!num[j]){
				continue;
			}
			num[j] = false;
		}
	}

	for(int i = 0; i < MAX; i++){
		if(num[i]){
			cout << i << " ";
			count++;
			if(count == 10000000){
				cout << endl << "Finished!" << endl;
				break;
			}
		}
	}

	finish = clock();
	cout << (finish - begin) / 1000 << "ms" << endl;

	delete[] num;
	return 0;
}

1 000 万番目の素数は 179 424 673 らしい*1ので最大値は 180 000 000 とした．
プロセッサは Core i5 の 1.3GHz．
で，実行結果．

何も工夫してないのでこんなものか．
偶数を飛ばすように書き換える．

#include <iostream>
#include <ctime>
using namespace std;
#define MAX 180000000

int main(){
	int count = 0;
	clock_t begin, finish;
	begin = clock();
	bool *num;
	num = new bool[MAX];

	for(int i = 2; i < MAX; i += 2){
		num[i] = false;
		num[i + 1] = true;
	}

	num[0] = false;
	num[1] = false;
	num[2] = true;

	for(int i = 3; i * i <= MAX; i += 2){
		for(int j = i * i; j <= MAX; j += i * 2){
			if(!num[j]){
				continue;
			}
			num[j] = false;
		}
	}

	for(int i = 0; i < MAX; i++){
		if(num[i]){
			cout << i << " ";
			count++;
			if(count == 10000000){
				cout << endl << "Finished!" << endl;
				break;
			}
		}
	}

	finish = clock();
	cout << (finish - begin) / 1000 << "ms" << endl;

	delete[] num;
	return 0;
}

実行結果．

かなり速くなった．
まだ無駄な繰り返しがあるので速く出来るとは思うが，思い付かなかったので良さそうな方法を見つけたらまた書く．

*1:http://primes.utm.edu/curios/page.php/179424673.html