

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

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

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

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


CC BY-SA 4.0
2020-09-30T08:02:21.077
70834
2020-09-30T16:36:18.533
2020-09-30T16:36:18.533
3060
41837
question
c
エラトステネスの篩をC言語で実装


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

そして、配列の２番目からN番目の値を１にする（まだ、篩から落とされていないことを１で表す）

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

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


CC BY-SA 4.0
2020-09-30T09:01:53.323
70838
2020-09-30T09:01:53.323
217
70834
answer


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

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

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

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

[code]

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

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

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

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

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

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


CC BY-SA 4.0
2020-09-30T09:44:32.430
70840
2020-09-30T09:44:32.430
19110
70834
answer