素数の見分け方は?素数かどうか調べる方法は?

スポンサーリンク
デフォルト 0未分類

素数の見分け方には簡単なやり方はあるんでしょうか?

小学生でも3ケタ以上の数の、2や3や5でも割れないような数が素数かどうか調べる方法はある?

スポンサーリンク

素数の見分け方は?

素数は1とその数しか約数がない数(1は除く)のこと

81までなら九九で見覚えのない数字は大体素数です。20まででいえば1、2、3、5、7、11、13、17ぐらいです。

素数でないと簡単に判るのは、2の倍数、3の倍数、5の倍数くらいでしょうね。

又、2乗や3乗程度の倍数なら、簡単に見分けられます。

しかし、一般に或る数nの約数を見つけるには、2~√n(の整数部)まで割ってみないと判らないでしょう。

例えば1万!+1(1万!=1×2×3×・・・×10000)は10000までの数では割り切れません(常に余り1)。

この数が素数とは限りませんが、素数か否かを判断するのは現実的に無理です。

尚、もっと桁が大きくなると ミラー・ラビン法 といったフェルマの小定理を利用した判定法がある。

ここに「ミラー-ラビン素数判定法」による素数判定サイトがあります。
相当大きな数(400桁くらいでも)でも判定できます。

素数判定(ミラー-ラビン素数判定法) - RSA暗号デモサイト
公開鍵暗号方式の一つであるRSA暗号では素数が重要なアイテムとなります。ここでは、ミラー-ラビン素数判定法による素数判定のデモを行います。

素数かどうか調べる方法は?

129を例に出します。

11^2 = 121
12^2 = 144

より、仮に129が素数でない場合、
(12より小さい数) * (12より大きい数)
で表すことができます。

なぜなら、
(12より大きい数) * (12より大きい数)
は144より大きくなってしまい、
(12より小さい数)* (12より小さい数)
= (11以下の数) * (11以下の数)
は121以下になってしまうからです。

なので、12より小さい素数で129を割っていき、割り切れるものがなければ素数となります。

結論としては、「素数判定したい整数nに対し、n > l^2となる最大の l を求め、 l 以下の素数で割っていく」です。

いずれにしてもだいたいでもよいので √n 以下の素数で割り切れるかを確認していきます。

タイトルとURLをコピーしました