[c言語] エラストテネスの篩

C言語

前回の内容で配列をやりましたが、これで繰り返し文なども勉強して、やれる範囲がとても広がったと思います。そんなことで、今日はエラストテネスの篩をやっていきます。

自然数kが素数である

  • √k以下の全ての素数で割り算を行い、割り切れなければkは素数である。

ー例えば、23が素数であるか判定するためには、4<√23<5なので、4以下の素数、すなわち2、3で割り切れないことを確認すれば良い。

エラストテネスの篩の処理の流れ

  1. 計算しようとする素数の最大値Nをオブジェクト形式マクロで指定する。
  2. int型の配列p[N+1]を宣言し、全ての要素を0で初期化する。
  3. iを2から小さい順に√nまで動かしながら、p[i]が0か1かを判定する

ーp[i]=0のとき、iの倍数j(= i*2, i*3, ・・・)は素数にはなり得ないので、p[j]に1を代入する。

ーp[i]=1のときは何もしない。

 4.  3の処理を終えたとき、p[i]=0である i が素数である。

それではサンプルコードを見てみましょう。

#include <stdio.h>
#include <math.h>
#define N 300

int main(void){
  int i,j,m,cnt=0;
  m=sqrt(N);
  for(i=2; i<=m; i++){
    if(e[i]!=1){
      for(j=2*i; j<=N; j+=i)
        e[j]=1;
    }
  }

  for(i=2; i<=N; i++){
    if(e[i]!=1){
      printf("%3d ",i);
      cnt++;
  }
    if(cnt==10){
      printf("\n");
      cnt=0;
    }
  }

  printf("\n");

  return 0;

}

/*実行結果
  2   3   5   7  11  13  17  19  23  29 
 31  37  41  43  47  53  59  61  67  71 
 73  79  83  89  97 101 103 107 109 113 
127 131 137 139 149 151 157 163 167 173 
179 181 191 193 197 199 211 223 227 229 
233 239 241 251 257 263 269 271 277 281 
283 293 
*/

 このエラストテネスの篩は素朴な方法と比べると高速に素数を列挙できるので、

とても計算時間が少なくて済むのです。

変数cntは10個数字が入力されたら改行を合図するための変数です。

ぜひマスターしてください。以上で終了となります。

ありがとうございました!

コメント

タイトルとURLをコピーしました