<問題> N (1000以下のN) までの素数を求めよ
<実行結果>
N : 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
<ヒント>
解答例
#include <stdio.h>
#include <math.h>
#define N 50 // プログラム中のNという文字をおきかえ
void sieve (int n, int p[]); /* 引数は配列の先頭アドレス */
int main (void) {
int p[N+1];
int i,j;
/* �� p[2] - p[N]を１に初期化 */
for(i = 2; i < N+1; i++)
p[i]=1;
/* �� エラトステネスのふるい。各自、確認 */
sieve (N, p); /* 配列のアドレス */
/* �� 値が1のものは、素数 */
printf("N : %d \n", N);
for(i = 2; i <= N; i++)
if(p[i]==1)
printf("%3d", i);
printf("\n");
return 0;
}
void sieve (int n, int p[]) {
int i, j;
/* nは整数。実数型へキャスト（型変換）して平方根。
さらに、intに型変換される。小数点以下が切り捨てになるので <= 。
条件部にi*i < Nという書き方もうまい */
for(i = 2 ; i <= sqrt((float)n); i++)
if(p[i] == 1)
for(j = 2; i*j <= N ; j++) {
/* if [i*j] == 1 としていないので、重複して0を代入 */
p[i*j] = 0;
printf("filtered p[%d]\n", i*j);
}
}