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

C言語でもやってみました(Ruby版)。
※注意 この実装はまだ未熟なので、下の modify された実装を見て下さい。(2017/7/4)

#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スクリプトの見た目の簡潔さ、美しさは際立っていますね。

 
※追記(2017/7/4)
ちがった実装にしてみました。具体的には、入出力と「篩」の部分を分けました。「篩」もだいぶ改良しています。
eratosthenes1.c

#include <stdio.h>
#include <math.h>

int a[1000001] = {0};

int sieve(int max) {
    int i, j;
    
    for (i = 2; i <= sqrt(max); i++) {
        if (a[i] == 1) continue;
        for (j = 2; j <= (max / i); j++) a[i * j] = 1;
    }
    
    i = 0;
    for (j = 2; j <= max; j++) {
        if (!a[j]) a[i++] = j;
    }
    return i;
}

int main () {
    int max = 0;
    int size;
    
    printf("最大値:");
    scanf("%d", &max);
    if (max > 1000000 || max < 2) return 0;
    
    size = sieve(max);
    
    for (int i = 0; i < size; i++) printf("%d ", a[i]);
    printf("\n");
    
    return 0;
}

関数 sieve で実際に「篩」を実行しています。配列 a は作業用であり、また関数から帰ったときには結果が入っています。返り値 size は答えとして有効な配列の大きさです。つまり、配列 a に返り値 size だけ素数が格納されています。

main 関数は関数 sieve の前に求めるべき素数の最大値を入力し、帰ってきたあとに実際に標準出力に結果を出力しています。

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