STEP 6.2 （エラトステネスのふるい）

問題

エラトステネスのふるいを、プログラムにしよう。

下のプログラムテンプレートを使い、②にあたる部分を作成せよ。(関数にしてもよい）

実行例

n : 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

コメント

例題集

解答例

[プログラム] 

#include <stdio.h>
#include <math.h>
#define N 50 // プログラム中のNという文字を、50におきかえ

int main (void) {
    int p[N+1]; 
    int i, j, max; /* 外側、内側、√N  */

    max = sqrt((float)N); /* Nは整数。実数型へキャスト（型変換）して平方根。
        さらに、intに型変換されてmaxに代入。小数点以下が切り捨てになる。 */
   
/* ① p[2] - p[N]を1に初期化 */
    for (i = 2; i <= N; i++)
        p[i]=1;

/* ②  エラトステネスのふるい。各自、確認 */
/* もし素数ではないなら、素数番目の配列pは、0にしよう */
/* ② エラトステネスのふるい。ルートN以下の素数について、直接、素数の倍数を篩に。
i以上の数に倍数かどうかを割り算して判定すると、先週の解法2になってしまう。*/
    for (i = 2 ; i <= max; i++) /* 条件部 maxは切り捨てになっているから、
                        =がいる。なお、条件部にi*i < Nという書き方もうまい */
        if(p[i] == 1) /* if(p[i]) とするのもうまい。
            for(j = 2;  i*j <= N ; j++) 
                p[i*j] = 0; /* if [i*j] == 1 とチェックしていない。重複して0を代入 */
                
        /* 内側のループの別の例：iを繰り返し足しこんで倍数を得ていく方法。
　　　　　　j = 3*iなど、初期値の工夫もよい
            for(j = i; j <= N ; j+=i) 
                p[j] = 0;　        */

        /* こちらは誤り すべての数に倍数かどうかを余りで判定している 
            for(j = i; j <= N ; j++) {
                if(j%i == 0) 
                    p[j] = 0;      */



/* ③ 値が1のものは素数。 */
    printf("n : %d \n", N);
    for(i = 2; i <= N ; i++)
        if(p[i]==1) 
            printf("%3d", i);

    printf("\n");

    return 0;

}