エラトステネスの篩

エラトステネスの篩は素数判定法の代表的なアルゴリズムです。簡単に言えば、「１より大きい数の表から合成数を取り除き、残ったものを素数と判定する」ということです。

例えば、3000までの素数判定は次のようになります。

#include <stdio.h>
#define MAX 3000

int main(void)
{
  int i, j;
  int p[MAX];

  //---初期化---
  for(i=0 ; i<MAX ; i++) p[i] = 0;
  p[0] = 1;
  //---倍数を除外---
  for(i=2 ; i<=MAX/2 ; i++){
    for(j=2 ; i*j<=MAX ; j++){
      if(p[i*j-1] == 0)
        p[i*j-1] = 1;
    }
  }
  for(i=0 ; i<MAX ; i++){
    if(p[i] == 0)
      printf("%d\n", i+1);
  }

  return 0;
}