Top / 素数生成(エラトステネスの篩)
HTML convert time: 0.023 sec.

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

Last-modified: 2015-03-15 (日) 12:48:51

このページではエラトステネスの篩を使った素数生成を紹介したいと思います。

エラトステネスの篩とは
 指定された整数までの素数を見つけるためのアルゴリズム。
 このアルゴリズムでは素数が現れたらその倍数を消去することで試し割よりも計算量が少なくすることができる。
 
<アルゴリズム>
 2からXまでの箱を用意して、2から順にその倍数の箱を消していく。
 最後まで残っていた箱が素数となる。

/*                        */
/*    エラトステネスの篩     */
/*    Xまでの素数の表示    */
/*                       */

#include <iostream>
using namespace std;

#define X 100000 
 
int arr[X+1];

int main()
{
	cout << "エラトステネスの篩" << endl;
	cout << X << "までの素数" << endl;
 
	for (int i = 2; i <= X; i++){
		arr[i] = 1;            // まずすべての箱に1を入れる
	}

	for (int i = 2; i <= X; i++){
		if (arr[i]){             // i の箱が1ならば i は素数
               cout << i << " ";
			for (int j = 2; i*j <= X; j++){
				arr[i*j] = 0;       // i の倍数の箱を消す(リセットする)
			}
		}
	}
	return 0;
}

<高速化>
 ・偶数は考えない。
 ・考える数は2から√Xまででよい。
 (√Xよりも大きい素数でない数は√Xより小さい数ですでに消去されている)

/*                            */
/*    エラトステネスの篩         */
/*    Xまでの素数の表示(高速化)    */
/*                            */

#include <iostream>
#include <cmath>
using namespace std;

#define X 100000

int arr[X+1];

int main()
{
	cout << "エラトステネスの篩" << endl;
	cout << X << "までの素数" << endl;

	for (int i = 3; i <= X; i = i + 2){         // 奇数のみ考える
		arr[i] = 1;
	}

	for (int i = 3; i <= sqrt(X); i = i + 2){
		if (arr[i]){
			for (int j = 3; i*j <= X; j = j + 2){
				arr[i*j] = 0;
			}
		}
	}
 
        cout << "2 ";

	for (int i = 3; i <= X ; i = i + 2){
		if (arr[i]){
			cout << i << " ";
		}
	}
	return 0;
}