読者です 読者をやめる 読者になる 読者になる

エラトステネスの篩(C言語)

C言語でもやってみました(Ruby版)。

#include <stdio.h>

int a[100000001] = {0};
void set_f(int i, int max)
{
  int j;
  for (j = 2; j <= (max / i); j++) a[i * j] = 2;
  return;
}

int main(void)
{
  int max, i;
  printf("最大値:"); scanf("%d", &max);
  for (i = 2; i <= max; i++) {
    if (a[i] != 2) { a[i] = 1; set_f(i, max); }
  }
  for (i = 2; i <= max; i++) {
    if (a[i] == 1) printf("%d  ", i);
  }
  printf("\n");
  return 0;
} 

C言語では配列の長さを変数で指定できないので、バカでかい領域(1億)をわざわざ確保しています。

さすがに C言語で、1億以下の最大の素数でも、だいたい 7秒くらいで計算します(最大の素数のみを出力する場合)。結果は 99999989でした。


コンパイルした実行ファイルをアップロードしておきます(Windows用です)。
  エラトステネスの篩.zip 直
解凍して、eratosthenes.bat(バッチファイル)をクリックして下さい。入力する数値は、1000くらいがいいと思います。1億より大きい数は入れないで下さい*1。(大丈夫だとは思いますが、プログラムの実行は自己責任でお願いします。)

それにしても、Ruby版と殆ど同じことをやっているのですが、Rubyスクリプトの見た目の簡潔さ、美しさは際立っていますね。

*1:1億より大きい数を入れると、そのまま終了するようにしました。(PM16:59)