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

エラトステネスのふるい(素数判定) - (2010/06/12 (土) 18:20:13) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

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

素数表を生成するアルゴリズムにエラトステネスのふるいというものがあります。
まずはこのアルゴリズムなしで素数かどうか調べる方法を考えてみます。

 /*入力した値が素数かどうか識別するプログラム*/
 #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;
 }

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

素数表を生成するアルゴリズムにエラトステネスのふるいというものがあります。
まずはこのアルゴリズムなしで素数かどうか調べる方法を考えてみます。

#region(close, プログラム例)
 /*入力した値が素数かどうか識別するプログラム*/
 #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;
 }
#endregion







...