スクリーニング法を用いて1~n間の素数を得る
763 ワード
//フィルタリング法を用いて1~n間の素数構想を導いた:1~nの配列primeを用いて1~nの数が素数であるか否かを示す.prime[i]が0の場合、素数となります.(1)2から2*2からnまでの2の倍数を削除(2)残りのデータセットから最小の素数3を見つけ,3*2からnまでの3の倍数を削除(3)残りのデータセットから最小の素数xを見つけ,x*2からnまでのxの倍数を削除(4)残りの数セットが空になるまで(3)ステップを繰り返すとアルゴリズムは終了する.
#include
#define SIZE 100
int main(void) {
int prime[SIZE+1]={0};
int i=2;
int j=0;
int n=0;
int mid=0;
printf(" :");
scanf("%d",&n);
mid=n/2+1;
// 1~n
while(i<=mid) {
for(j=i+1;j<=n;++j) { // i
if(0==prime[j]&& 0==j%i) //
prime[j]=1;
}
++i;
while(prime[i]==1)//
++i; //
}
// , ,
for(i=1;i<=n;i++)
if(0==prime[i])
printf("%d ",i);
return 0;
}