例 1: 素数表の作成(エラトステネスの篩(sieve))

配列を用いたプログラムの例として, エラトステネスの篩法で 素数表を作成します. エラトステネスの篩は, 小さい素数から順に その数の倍数を消去していくことにより素数を残していく方法で, とても効率が良い事が知られています.

プログラムでは, isprime という文字型の配列に 素数であるか否かの判定結果を入れます. iが素数であれば, isprime[i] = 1, そうでなければ isprime[i] = 0です. ここで, 右辺値の 1, 0は(文字ではなく)数です.

プログラムの最初の方にある,

#define MAX 1000

は, マクロ置換で, この 1000の値を変えてコンパイルしなおせば, その値未満の素数表が出力されます.(ただし, 配列の添字が取れる範囲の 制限が付きます. この値は処理系依存です.) プログラム中で 1000 という値を陽に書いてしまうと, プログラムの変更の度に 4箇所の変更が 必要になり, プログラムのミス(バグ(bug)と言われる)の原因になりますので, このような工夫をします.

また, 配列も他の変数同様, 宣言した時の初期値は不定です. きちんと 初期化しないと, 誤動作の原因になります. ここでは, 配列の初期化は ライブラリ関数 memset を使って実行します. すなわち,

memset(isprime, 1, sizeof(isprime));

は, isprime[i] を全て 1にします. sizeof というのは, 変数のメモリに占める大きさを計る C言語の組み込み関数で, このような初期化で必ず使う物です. また, ライブラリ関数については, 出て来る度に 1度は man コマンドでその内容を確認するようにして下さい.

他の部分は, プログラムとその注釈を読んで下さい. Sieve processと いう部分が, 篩の実行部分です.

/* File name 6-3.c      */
/* Print primes to MAX  */

#include <stdio.h>
#include <math.h>
#define MAX 1000

main()
{
        char  isprime[MAX];
        int   i, j;
        double  sqrtmax=sqrt(MAX);
        
        memset(isprime, 1, sizeof(isprime)); /* Initialization */

        /* Sieve process  */
        isprime[0] = isprime[1] = 0;        /* 0 and 1 are not prime. */
        for (i=2; i <= sqrtmax; i++){
                if (isprime[i]==1){   /* i is prime. */
                        for (j=i; i*j<MAX; j++){
                                isprime[i*j] = 0; /* multiples of i are not prime. */
                        }
                }
        } /* The end of the sieve. */

        for (i=0; i <=MAX ; i++){ 
                if ( isprime[i]==1 )
                        printf("%d\n", i);
        }
}