スクリーニング法を用いて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;
		
}