第二十回　素数判定プログラム

やあ、こんにちは。今日は『素数判定プログラム』を作成してみよう。

素数判定プログラムとは、文字通り与えられた整数が素数かどうか判定してくれるプログラムのことだ。自分で好きな整数を入力して、それが素数ならば『素数』、素数でないならば『合成数』と表示するようにしたい。その前に、素数がどういうものかはもちろん知っているな？

うむ、大丈夫そうだな。実際にプログラムを書く前に少し準備をしよう。与えられた整数、例えばそうだな『1001』は素数かどうか調べてほしい。

うむ、その通りだ。因みに、1001＝7×11×13と因数分解されるぞ。さて、プログラムで与えられた整数が素数かどうか調べるときも、基本的には上でヒロトがやったのと同じ方法を取る。つまり、2から順に割り切れるかどうかチェックするのだ。

うむ、あとは割り切れるという状況をどう表現するかが問題だ。何か使えそうなものはあるかな？

うむ、方針が立ってきたみたいだな。では、そろそろプログラムを書いてみよう！

素晴らしい、とても短くまとまっていて見事なプログラムだ！2行目であらかじめ変数 a に『素数である』という文字列を代入したという工夫、簡単そうに見えてなかなか思いつかないものなので立派だぞ。

一つだけアドバイスをしよう！例えばかなり大きな整数が素数かどうか調べるとき、2からn-1まで割るのは効率が悪い。たとえば『1234567』という整数を上のプログラムで調べると数秒かかってしまうのだ。たいしたことないと思うだろうが、コンピュータで数秒はとてつもない作業をしていることになるのだ。

そういうことだ。そこで、作業の量を劇的に減らす方法を教えよう。結論から言うと、整数 n が素数であるかどうか調べるには、2から \(\sqrt{n}\) まで割り切れるかどうか調べれば十分なのだ。\(\sqrt{n}\) には小数が含まれることがあるため、int関数で切り捨てて整数を作り、for文の範囲を『range(2 , int(n**0.5)+1)』としてやればいいのだ。

ふふ、とても簡単な理屈なのだ。分かりやすさのため、例えば100を例にとって説明しよう。

\(\sqrt{100}=10\) であるから2から10まで100の約数があるかどうかチェックすればいい訳だが、10より大きい約数が存在するかどうかは調べる必要がないのだ。例えば、20は10より大きい100の約数であるが、これは100=20×5であるから5で割ったときに既にチェック済みなのだ。また、25も10より大きい100の約数であるがこれは100＝25×4であるから4で割ったときに既に調べている。

そういうことだ！

では、このことを踏まえて上のプログラムを修正してみよう！

うむ、このようにプログラムをより良くするためには数学的な知識も必要となることは覚えておいてほしい。では今日はここまでにしよう、お疲れさん。