タイトルのような質問を生徒からたまに受けます。
素数（1とその数自身以外に約数を持たない数）かどうかの判定は、慣れている人と慣れていない人でかなりスピードに差が出ます。大きい整数が素数かどうかを確認したい場面は結構ありますので、今回の記事で紹介するやり方を知っているだけで得する場面は多いです。
さて、503が素数であるかどうかを確認するためには、基本的には503を割ることができる数があるかどうかを、小さい数から順に試していく必要があります。
多くの生徒は、素数で割れるかどうかだけ確かめれば良いことは知っています。もし合成数（素数ではない数）で割れるのであれば、その前にその合成数の素因数で割れるはずだからです。たとえば、503÷21が割り切れるかどうかは考える必要がありません。なぜかというと、503÷21＝503÷3÷7なので、503÷3が割り切れない時点で、503÷21も割り切れるはずがないからです。
しかし同時に、多くの生徒は「503までのすべての素数で割らないと素数であることは確定しない」と思っています。
しかし、実際には\(\sqrt 503\)（2回かけて503になる正の数）以下の素数で割るだけで、503が素数であるかどうかを確認することができます。\(23^2＝529\)なので、23未満の素数で503を割り切ることができるかだけ確認すれば良いということです。
つまり、やるべき計算は以下の8つだけです。
- 503÷2
- 503÷3
- 503÷5
- 503÷7
- 503÷11
- 503÷13
- 503÷17
- 503÷19
これくらいの計算は1分以内にできるような計算力は欲しいですね。
ちなみに、たとえば503÷17が割り切れるかどうかは、「503＝17×30ー7だから17では割り切れない」のように判断できると、単純に割っていくよりも速く確認できます。この方法は、17×3＝51を覚えているからできることです。
さて、なぜ「\(n\)が素数であるかを確認するためには\(n\)を\(\sqrt n\)以下の素数で割るだけで良い」のかですが、これは「約数には必ずペアがいる」ことからわかります。
たとえば、24の約数は「1，2，3，4，6，8，12，24」の8つですが、これらを以下の表のように、上下の積がどこでも24になるように並べることができます。
| 1 | 2 | 3 | 4 |
| 24 | 12 | 8 | 6 |
約数をすべて書き出すときに漏れが出てしまう人も多いですが、このようにペアを作りながら探すことで、漏れが出る可能性をかなり減らすことができます。
ここでポイントとなるのは、「24の約数を探すにあたっては、上段の1，2，3，4を見つけ終わった時点で、残り4つについてはすでに見つけたようなものである」ということです。残りは24÷1，24÷2，24÷3，24÷4で簡単に見つかるからですね。
ここで、上段の一番大きい数は4で、下段の一番小さい数は6になっています。上段と下段が切り替わる地点を「折り返し地点」と呼ぶことにすると、「24の約数の折り返し地点は4と6の間」ということになります。
ペアはすべて積が24なので、上段の数は「2回かけて24になる数」よりも小さく、下段の数は「2回かけて24になる数」よりも大きいはずだということがお分かりでしょうか。「2回かけて24になる数」というのは\(\sqrt 24\)のことなので、折り返し地点は\(\sqrt 24\)（\(\sqrt 25\)＝5より少し小さい数）であることがわかります。
ですから、約数をすべて探すためには、\(\sqrt n\)までの約数（上段の約数）を探せば、下段の約数は自動的に見つかるということです。
これで、「503が素数かどうかを調べるためには、\(\sqrt 503\)までの素数で割るだけで良い」ことの意味が分かったはずです。折り返し地点の\(\sqrt 503\)までに約数がないのであれば、それ以上探しても約数はないということです。
次回の記事：「1313/63は約分できますか？」←10秒で答える方法に続きます。
コメント