素数判定プログラムを作ってみた
久々にブログの更新です。ちょっと忙しくって、更新できない日々が続いてしまいました。
僕は最近素数判定プログラムを作った。
まず、素数は何かというと、「1とその数でしか割り切れない数」。
まあ、例を挙げると、2, 3, 5, 7, 11 とかだ。
この素数の面白い覚え方に、
「兄(2,3)さん5時(5)にセブン(7)イレブン(11)父さん(13)いいな(17)とついていく(19)」、兄さん(23)肉(29)屋にさあ行(31)こう皆(37)良い(41)シーサー(43)しない(47)でゴミ(53)に」…。
全部書いているときりがないので、ここまでしか書かないが、1から103までの覚え方がある(らしい)。というような覚え方がある(らしい)。
まあこの覚え方は置いといて、この素数について話題を戻そう。
僕の作った素数発見プログラムは、スクラッチ(👇)で作ったもので、とても早くその数が素数かを判定できる。
例えば、1234567891(素数)を入力すると、
3秒くらいで「素数」と書かれた画面が表示される。
このプログラムは、旧型から進化して生まれたプログラム。
第1号、僕が作った第1号プログラムは、その数まで全ての数で割っていくプログラム。
ちなみに1234567891を素数だと判定するのに12時間以上かかった(途中でもうやる気が失せて、最後まで試さなかった)。
第2号、第2号は、その数割る2の数まで調べていくプログラム(例えば、6を入力すれば、6÷2=3まで調べる)。
でも、これも1234567891には、6時間くらいかかる。
第3号、第3号で、僕は、その数の平方根(例えば、4だと2、81だと9だというような数)まで調べればいいことに気がついた。(平方根以上の数とのペアは、片方はもう平方根より小さい数としてチェック済みだから)なので、格段に早くなり、6秒くらいで、1234567891をで断定できるようになった。
第4号、第4号は、第3号で調べるときの速さが2倍になるように、2で割るか調べた後は、もう2の倍数は調べなくていいようにした(2の倍数か調べた後は、偶数は調べないということ)。つまり、3秒くらいで断定できるようにした。
でも、この第4号には欠点があって、本当に大きすぎる数は、素数か調べようとしないこと。
今度はこれを直したいけど、難しそう…。
にほんブログ村のランキングに参加しました。
面白かった人は下のバナーをポチッとお願いします↓
僕とスクラッチについてはこちら👇