「エラトステネスのふるい(素数判定)」の編集履歴（バックアップ）一覧に戻る

エラトステネスのふるい(素数判定) - (2010/06/12 (土) 18:30:37) の編集履歴(バックアップ)

---

エラトステネスのふるい(素数判定)

素数表を生成するアルゴリズムにエラトステネスのふるいというものがあります。
まずはこのアルゴリズムなしで素数かどうか調べる方法を考えてみます。
ある数が素数かどうか調べるにはその数がその数より小さい数すべて(1以外)で
割り切れない場合素数なのでfor文で回せば簡単にコーディングできそうです。

プログラム例

/*入力した値が素数かどうか識別するプログラム*/
#include <stdio.h>

int main(void){
	int n, i, flag;

	while(1){
		flag = 1; //変数の初期化

		//数値の入力
		printf ("数値を入力してください:");
	   	scanf ("%d", &n);

		if(n==0)break; //0だったら終了

		//1は素数でない
		if(n==1)
			flag = 0;

		//ある数を2から(a-1)まで割って割り切れるか調べる
		for ( i=2 ; i<n ; i++ ){
			if ( n%i == 0){ //割り切れたら素数でない
				flag = 0;
				break;
			}
		}

		if(flag==0)
			printf ("数値は素数ではありません\n");
		else
			printf ("数値は素数です\n");
	}
	
	return 0;
}

次ににエラトステネスのふるいをコーディングします。
wikidediaのエラトステネスの篩に詳しい説明があるのでここでは説明しません。
以下がプログラム例です。

/*1000000までの素数をすべて出力するプログラム*/
#include<stdio.h>
#include<math.h>

// 過去問に合わせています。
#define MAX 1000000

int main(void){

	//char型にすることでbyte幅が1byteで済む
	char p[MAX+1];
	int i,j;

	// 0,1は素数でないので0を代入する
	p[0]=0;
	p[1]=0;
	for(i=2; i<=MAX; i++)p[i]=1;

	// +1の理由:
	// めったにないが、環境によってsqrt(4)=1.99...になり、
	// iがint型なので小数点以下が切り捨てられしまうため。
	for(i=2; i<=sqrt(MAX)+1; i++)
		if(p[i]==1)
			// 倍数を消していきます（素数でないものに0を入れる）。
			for(j=i*2; j<=MAX; j=j+i)p[j]=0;

	// Output
	for(i=0; i<=MAX; i++)
		// 配列の中身が１だと素数です。
		if(p[i]==1)
			printf("%d ",i);
	puts(""); 
}

...