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

問題

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

実行例

どのようなふるい（フィルター）をしているのかを出力 
filtered p[4]
filtered p[6]
filtered p[8]
filtered p[10]
filtered p[12]
filtered p[14]
filtered p[16]
filtered p[18]
filtered p[20]
filtered p[22]
filtered p[24]
filtered p[26]
filtered p[28]
filtered p[30]
filtered p[9]
filtered p[12]
filtered p[15]
filtered p[18]
filtered p[21]
filtered p[24]
filtered p[27]
filtered p[30]
filtered p[25]
filtered p[30]
N : 30
  2  3  5  7 11 13 17 19 23 29

コメント

例題集

解答例

[プログラム] 

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

void sieve (int i, int n, int p[]);
void filter (int i, int m, int n, int p[]);

int main (void) {
    int p[N+1]; 
    int i;

/* ① p[2] - p[N]を１に初期化 */
    for(i = 2; i <= N; i++)
      p[i]=1;

/* ② エラトステネスのふるい。 再帰版の呼び出し */
    sieve (2, N, p);

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

    printf("\n");

    return 0;
}

/* 再帰版 */
void sieve (int i, int n, int p[]) {
    if (i <= sqrt((float)n)) { /* 再帰条件 */
        if (p[i] == 1) /* もし、素数なら */
            filter (i, 2, n, p); /* 後ろをフィルター */
        i++;
        sieve(i, n, p); /* 次のiから後ろをエラトステネス */
    }
  /* 停止条件は、何もしないので、プログラムしない */
}

void filter (int i, int m, int n, int p[]) {
    if (i*m <=n) { /* 素数iのm倍 */
        if (p[i*m] ==1) { /* 1になっているかどうかをチェック。繰り返し代入になるが、しなくてもよい */
            p[i*m] = 0;  /* 素数ではない */
            printf("filtered p[%d] \n", i*m);
        }
        m++;
        filter (i, m, n, p); /* 次のmについてfilter */
     }
   /* 停止条件は何もしない */
}