【課題４−１４】　提出課題（６）
コマンドラインから入力した整数値までの素数を，「エラトステネスのふるい」のアルゴリズムを用いて求めるプログラムを，空欄のＡ〜Ｄを埋めて作成せよ．

#include <stdio.h>
#include <stdlib.h>

#define N 100

int main(int argc, char *argv[]) {
	char prime[N+1] = {0}; //素数のふるいを0で初期化
	int i, j, n;
	
	if (argc < 2) {
		printf("This command requires an argument.¥n");
		return 0;
	}
	
	n = 「　　Ａ　　」; //要求された数を整数変換
	if (n > N)
		n = N;
	
	for (i = 2; i <= n; i++) {
		if (prime[i] == 「　Ｂ　」) { //まだ倍数でなければ
			// 2*倍数から要求数まで倍数分増加してループ
			//　その数のフラグを立てる（要素に１を代入する）
			for (j = 2 * i; j <= n; j「　Ｃ　」)
				prime[j] = 1;
		}
	}
	
	for (i = 2; i <= n; i++) //フラグが立ってない数を表示
		if (「　　Ｄ　　」)
			printf("%4d", i);
	
	return 0;
}



【実行結果例】
	prompt% ./sample 20
	2   3   5   7  11  13  17  19

【解説とヒント】
ある数nまでの素数を求めるには，素直にループで，2からn-1までの数で，割り切れない数を取り出してもよいのだが，ここでは「エラトステネスのふるい」という簡単で高速なアルゴリズムを用いている．
エラトステネスのふるいは，ふるいに入れた数から2の倍数を消去，3の倍数を消去，というように，順にnの倍数までを消去し，残った数を素数として取り除く．