Top / 素数生成
HTML convert time: 0.026 sec.

素数生成

Last-modified: 2015-03-17 (火) 22:26:36

素数は1とその数でしか割ることができないという素数の性質を使う。まずは簡単なプログラムを書いてみます。下にあるプログラムは指定された数までの素数を表示させるプログラムです。2からはじまり、3,4,5・・・・と数を増やしていき、その数は1,2,3・・という数字で割り切れるか?というプログラムを書いています。そして、1とその数字の2通りしか割り切れなければ、(ここではkの値の2)それは素数だということになります。

/*                          */
/*     Xまでの素数の表示       */
/*                          */  
#include <iostream>
using namespace std;

#define X 1000 
 
int main()
{
	cout << X << "までの素数" << endl;

	for (int i = 2; i <= X; i++){
		int k = 0;
		for (int j = 1; j <= X;j++){
			if (i%j == 0){
				k++;
			}
		}
		if (k == 2){
		        cout << i << " ";
		}
	}
	return 0;
}

このように全部わってみる素数判定法を「試し割り」と言います。非常にシンプルでわかりやすいです!しかし、この方法だと無意味な計算も含まれています。たとえば、1,2,3,4,5,6,7,8・・・という数で割っていく場合、4で割り切れるのであれば、すでに2で割り切れるということになります。同じく6も8も同様です。このように考えると、2以外の偶数は素数ではないのでその数を計算させなければ、処理も高速化できるはずです。そのほかにも高速化させるための考え方を以下に示します。

<高速化>
 ・2以外の偶数は素数ではないので考えない。
 ・Xが素数かどうか知るためには√Xまで考えればよい。
 (√Xよりも大きい数で割れるのなら√Xよりも小さい数でも割れるはずである)
 ・√Xまでで1以外で1回でも割れたら終了する。


プログラムを書いてみます。

/*                                */
/*     Xまでの素数の表示(高速化)    */
/*                                */

#include <iostream>
using namespace std;

#define X 1000

int main()
{
	cout << X << "までの素数" << endl;
       
        cout << "2 ";

	for (int i = 3; i <= X; i = i + 2){      // 奇数について
		int k = 0;
		for (int j = 1; j <= sqrt(i);j = j + 2){
			if (i%j == 0){
				k++;
			}
			if (k > 1){
				break;
			}
		}
		if (k == 1){
			cout << i << " ";
		}
 	}
	return 0;
}