-1

学校の課題で「エラトステネスの篩を用いて100以下のすべての素数とその個数を表示するプログラムを作成せよ。」との課題が出題されたのですが、ヒントを読むなり先生からの説明を聞くなりして、原理は理解できたのですが、何からプログラムを書き始めていいのかが全くわかりません。

ちなみに、与えられたヒントを下記に示します。

ヒント:
ステップ1:2からNまでの整数をすべて篩いに入れる。m=1をする。
ステップ2:篩に残ったmより大きい最小の数をnとする。n>√Nであればステップ4へ
ステップ3:nの倍数をすべて篩から落とす。(これらはnの倍数なので素数ではない。)
m=nとする。ステップ3へ。
ステップ4:終了。篩に残っている数が素数である。

上記にも記したように、何からプログラムを書き始めればいいのかがわからないというのは、int... ,void... , int main()..., while文など、数え切れないほどあるc言語の中から、何を用いれば課題解決に近づくのかがわからないということです。
プログラミングをしてから間もない上に、かなり丸投げの質問になっているかもしれませんが、ご回答よろしくお願いします。

0

2 件の回答 2

3

まずは、どのようなデータを使う必要があるかを考えます。ヒントには「篩」というのが出てきますが、これは C 言語に用意されているものではありません。どのような仕組みを使えば「篩」が作れるでしょうか?

ヒントに出てくる「篩」の条件を見てみると、「篩」には「ある自然数が残っているか、残っていないか」が表現できる能力が求められていそうです。

これを C 言語で表現するやり方はいくつかありますが、たとえば配列を使ってみるのはどうでしょうか。つまり、int furui[] のように配列を作ると、ちょうど配列の添え字が自然数になるので、「自然数 i が残っていない」を「配列の要素 furui[i]0」みたく表現することができます。なお、ここで 0 としているのは適当に 0 を選びました。0 だったら残っていない、0 以外だったら残っている、と勝手に決めてみます。

ここまで決めれば、次はヒントにあるステップをプログラムの形にしていきましょう。たとえば「2 から N までの整数をすべて篩に入れる。」というのは、篩に対して 2 から N までが「残っている」とすれば良いのですから、以下のように書けそうです。

for (int i = 2; i <= N; i++) {
    furui[i] = 1;
}

これで furui[2], furui[3], ..., furui[N] までが 1 になって、「篩に残っている」という状況が表現できていそうです。

いや、ちょっと待ってください。このように書くためにはまず配列 furui を定義し、初期化しないといけないはずです。添え字 N までは必要なので、配列の長さは N + 1 でしょうか。これを書かねばなりません。

そういえば N とは何でしょうか。いま求めたいのは 100 までの素数なので、元から N を使わずに表現できそうですね。

さらに C 言語では関数の中に処理を書くのが普通です。よくあるように int main() { ... } の中で処理が必要です。

……と、このように、自然言語で書かれた処理を細かく分解し、それぞれに対して細かくプログラム側での概念をあてはめていけば、プログラムを書いていくことができそうです。

1

とりあえず、2からNまでの値をいれておくところ(配列とか)を用意しましょう。
(大きさNの配列があれば、全部入りますよね)

そして、配列の2番目からN番目の値を1にする(まだ、篩から落とされていないことを1で表す)

配列のnの倍数番目を0にしていくことで、nの倍数を篩から落としていきます。

まぁ、こんな感じで考えたらどうでしょうか?

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。