演習問題 1 (素数 - prime number)

2以上の整数を入力して, その数が素数かどうかを判定するプログラムを作ってみよう. (素数とは, 1 とその数以外に約数を持たない数のこと - 念のため.)

といっても, いきなりこれでは難しいかも知れないので, 順をおって「段階的に」プログラムを作っていこう. (必ずしも下記のステップをそのとおり進める必要はない; 自分ができそうなレベルをやってみて, 難しかったら一つ前に戻ると良いだろう.)

割算の余り(剰余)の出力 (「基礎プロくん」を使うなら, 課題 1)
まず, 自然数 j をひとつ入力して, 1 から j までの整数で j を割った余りを順番に出力するプログラムを作ってみよう. (剰余を求める演算子は「%」だった - 念のため.) 入力として 6 を与えた時に, 出力はたとえばこんな感じになる:
```
6 mod 1 -> 0
6 mod 2 -> 0
6 mod 3 -> 0
6 mod 4 -> 2
6 mod 5 -> 1
6 mod 6 -> 0
```
約数だけを出力 (「基礎プロくん」を使うなら, 課題 2)
前のプログラムを改良して, 約数だけを出力するようにしてみよう. 同じく 6 を入力した時の出力はこんな感じ:
```
1
2
3
6
```
(約数かどうかの判定は, 剰余が0かで決定できる - 念のため)
約数の個数を出力 (「基礎プロくん」を使うなら, 課題 3)
前のプログラムをさらに改良して, 約数の個数を出力するようにしてみよう. 同じく 6 を入力した時の出力はこんな感じ:
```
4
```
約数の個数を調べるには, 個数をカウントする変数を新しく宣言して, 約数が見つかるたびにそれを1ふやしていけばよい. (いつもの数え方)
素数かどうかを出力 (「基礎プロくん」を使うなら, 課題 4)
前のプログラムをさらに改良して, 最初に入力した数 j が素数かどうかを判定するプログラムにしよう. 素数だったら「is prime」, 素数でなかったら「is not prime」と出力させる. 同じく 6 を入力した時の出力はこんな感じ:
```
6 is not prime
```
(約数の個数がわかったから, 素数かどうかの判定は容易.)
(ここからは, 余裕があれば, の話) 計算の手間を改善
ここまでのプログラムでは, 1 から j まですべての数で割算をやっていた. しかし, 考えてみればずいぶん無駄な計算をしている:
- 1 や j で割って割り切れるのは自明.
- j/2 より大きい約数はありえない.
- もっといえば, j の平方根以下の約数がないなら, それより大きな約数もないはず.
- あるいは, j が奇数の場合, 偶数の約数を持つことはありえない.
このあたりを利用すると, 割算をやってみる数の範囲をぐっとしぼることができる. これはつまり, 計算の手間を減らしていることになる.
また, 小さい数から順次割算をしていく途中で, 割り切れる場合がひとつでも見つかったら素数でないことはあきらかだから, その先を計算することは無駄である. この無駄を省くにはプログラムをもう少し工夫しないといけない.

[page 3] prev index next