素数を羅列するプログラム

プログラミングを学びたての頃に素数を羅列するプログラムを書いていたのでここにも貼っておこうと思います。

その時は知らなかったのですがエラトステネスの篩(ふるい)という素数を探すアルゴリズムがあるみたいですね。

これも実装しましたので下に書いておきます。

使用言語はC言語です。

約数の数が2個以上だと素数だと判断するアルゴリズム

ここでの約数は1とその数自身です。

その２つだけで割ることのできる数は素数で判断します。

逆に1と自分自身以外で割ることができたら素数から排除します。

フローチャート

ソースコード

#include <stdio.h>

int main(){
  int a = 100;
  int i,j;
  int div_num;

  for (i = 1; i <= a; i++) {

    div_num = 0;

    for(j=1;j<=i;j++){
      if(i%j==0){
        div_num++;
      }
    }
    if (div_num==2) {
      printf("%d\n",i);
    }
  }
  return 0;
}

エラトステネスの篩(ふるい)

参照: エラトステネスの篩 - Wikipedia

ソースコード

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
int main (){
    int a = 50;
    int sq_a = (int)sqrt((double)a);
    bool list[a];

    int i,n,m;
    //ステップ1
    for(i = 0;i <= a ; i++){
        list[i] = true;
    }
    //0,1は素数じゃないので
    list[0] = false;
    list[1] = false;

    //このforがステップ2の繰り返しなので
    //ステップ3
    for (n=2; n<=sq_a;n++) {
        //ステップ2
        if (list[n] == true) {
            for (i = 2; n*(i-1) < a; i++) {
                list[n*i] = false;
                //素数の整数倍は素数じゃないのでfalse
            }
        }
    }
    //ステップ4
    //出力
    for(i=0;i<=a;i++){
        if (list[i]) {
            printf("%d\n",i);
        }
    }

    return 0;
}