素数判定法 | エラトステネスのふるいに関連して、ガウス記号を使わない改造した判定法を解説
“素数判定法 “について、エラトステネスのふるい （篩）を算数で学習した内容から少し工夫をします。
すると、1万以下の自然数について、100以下のどの素数でも割り切れなければ素数と断定できます。
例えば、509 が素数かどうかということを判定することができます。3 ケタや 4 ケタの整数について、約数が 1 とその数以外にあるかどうかを効率的に判断できる方法になります。
ふるいにかけて、分数がこれ以上約分できるかどうかといった悩みは解消です。
分数を答えとするときに、もうこれ以上約分できない形にします。4/6 なら分母と分子を 2 で約分をして、2/3 を答えとします。
では、157/191 という分数ではどうでしょうか。これ以上約分できるのか、それともこれ以上は約分ができなくて、このまま答えとして良いのか。
この手の 3 ケタや 4 ケタの分数について、素数かどうかということを判断することが大切になります。
※ 最大公約数を求めるという方法もありますが、このブログ記事では、素数かどうかということに焦点を当てて議論をしています。
素数とは、2 以上の自然数で、約数が 1 とその数自身しかない自然数のことです。別の言い方をすると、正の約数が 2 個しかない自然数を素数といいます。
例えば、5 だと正の約数が 1 と 5 の 2 個しかないので素数です。
2 も同じく正の約数が 2 個しかないので素数です。しかし、1 は正の約数が 1 個しかないので素数ではありません。
自然数は素因数分解といって、素数ばかりの積の形で表すことができます。
ここで問題になるのは、分子や分母に使われている自然数が素数かどうかです。
分数だと分子と分母を素因数分解して、共通に使われている素数で分子と分母を約分することで、より小さい数にできます。
この素数の簡単な見分け方をこれから解説します。
先ほどの素数の定義に基づいて、2, 3, 5, 7, 11, 13 が素数ということを直接計算して確かめられます。
しかし、13 くらいになってくると、約数かどうかを判断する自然数が 13 個もあって大変になります。
そこで、素数判定を行う方法がないかと思うわけです。実は、3 ケタや 4 ケタくらいなら、手計算で素数かどうかを判定する方法があります。
まず、その判定法の根拠となる整数分野の数学の定理を紹介します。
素数判定法 :まずは使い方から
この【定理】は古典的な整数論において知られたものです。
ただ、多くの中学生や高校生の方が、この【定理】を使って、テスト中に素数かどうかを判定できるかというと、苦しいものがあるかと思います。
例えば、503 のルートは、だいたいどれくらいで、しかもそれを越えない整数は何か。ルートを取った値を小数で近似するという過程があるので、大変です。
昔の私のように、悩まないためにも、もっと使いやすい形で、3 ケタや 4 ケタの素数を判定する方法をこれから説明します。
定理を緩めて使う
【定理をカスタム】
a を自然数とする。
自然数 n が n2 ≧ a を満たしたとき、n 以下のすべての素数が a を割り切らなければ、a は素数である。
実は、先ほどの定理よりも、a を割り切るかどうかを調べる必要がない素数について調べてしまうときも出てきます。
ここが改造（カスタム）したことのデメリットです。
しかし、ルートをとって、それを越えない最大の整数 z を見つけることを思うと、3 ケタや 4 ケタくらいの自然数の素数判定だと、大した時間と労力のロスにはなりません。
では、実際にこのカスタムした方で、素数かどうかを判定してみます。
17 という自然数が与えられたときに、まず二乗して 17 以上となる自然数 n を 1 つ見つけます。そして、n 以下の素数すべてについて、17 を割り切るかどうかをチェックします。
※ 同じ数を 2 個掛け合わせることを二乗といいます。
5 の二乗は 25 なので、17 以上です。これで、定理カスタムの n として 5 が見つかりました。5 以下の素数は、2 と 3 と 5 です。
2 と 3 と 5 は、どれも 17 を割り切れません。よって、定理カスタムから 17 は素数ということになります。
【定理】のままだと、17 にルートをつけた値を越えない最大の整数を見つけるという過程が必要です。
二乗して 17 以上となる自然数を見つける方が、ずっと楽です。その代わりに、少しだけ遠回りをしています。
遠回りは許容範囲
【定理】の通りに素数判定を行うと、2 と 3 だけで素数判定できていました。
定理カスタムの方では、5 を調べる必要が無いのに、わざわざ 17 を割り切るかどうかを調べてしまっていました。
しかし、17 にルートをつけた値を越えない最大の整数が 4 ということを調べることを思うと、定理カスタムの方は、二乗するだけなので抵抗感が小さいかと思います。
ただ、定理カスタムの方は、遠回りをしていますが、【定理】で述べられている割り切るかどうかを調べなければならない素数について、すべて調べています。
ルートを小数で近似することを考えると、定理カスタムで判定を行った方が、中学生や高校生の方にとっては気分が楽かと思います。
25以下の素数判定
自然数 a について、
n2 ≧ a を満たす n を 1 つ見つける。
次に、n 以下のすべての素数が a を割り切るかどうかをチェックする。
この定理カスタムの手順で 25 以下の素数を調べてみます。
19 という自然数を a とします。
52 ≧ 19 より、n として、5 が見つかりました。5 以下の素数は、2 と 3 と 5 なので、これら 3 個の素数が 19 を割り切るかどうかを確認します。
2 と 3 と 5 のどれも、19 を割り切らないので、19 は素数です。
次に、52 ≧ 23 で、2 と 3 と 5 のどれもが 23 を割り切らないので、23 は素数です。
素数判定法 :100以下の素数判定
10 の二乗は、102 = 100 です。そのため、100 以下の自然数については、10 以下の素数である 2, 3, 5, 7 のすべてで割り切ることができなければ、素数ということになります。
たった 4 個の素数で割り算をして割り切れるかどうかを調べるだけなので、100 以下の自然数についての判定は楽です。
例えば、71 は素数かどうかを調べます。
71 = 2 × 35 + 1,
71 = 3 × 23 + 2,
71 = 5 × 14 + 1,
71 = 7 × 10 + 1,
71 は、2 と 3 と 5 と 7 のどれで割っても割り切れないので素数です。
49以下の素数
3 ケタや 4 ケタの自然数が素数であるかを判定するために、49 以下の素数を押さえておくと心強いです。
暗記をすると、思い違いをしているか気になるかもしれないので、確実に拾い上げておきます。
2, 3, 5, 7, 11, 13, 17, 19, 23 まで素数ということを調べています。24 以上の偶数は 2 で割り切れるので、素数でないことが分かります。
そこで、奇数について調べます。72 = 49 なので、7 以下の素数である 2, 3, 5, 7 で割り切れるかどうかです。偶数は先に除きますから、3, 5, 7 で割り切れるかどうかです。
25 = 5 × 5, 27 = 3 × 9, と九九の計算で素数でないことが分かりました。次の奇数は 29 です。
29 は、3 と 5 と 7 で割り切れないので素数です。31 も同じく素数です。33 = 3 × 11 なので素数ではありません。35 = 5 × 7 なので素数ではありません。
37 は 3 と 5 と 7 で割り切れないので素数です。39 = 3 × 13 だから素数ではありません。41 と 43 は 3 と 5 と 7 で割り切れないので素数です。
45 = 5 × 9 なので素数ではありません。47 は 3 と 5 と 7 で割り切れないので素数です。49 = 7 × 7 なので素数ではありません。ついでに、50 は 2 で割り切れるので素数ではありません。
キリの良いところまできましたので、まとめておきます。
【50以下の素数】
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 が素数です。
全部で 15 個です。
50 の二乗は 2500 なので、2500 以下の自然数については、これらの 15 個の素数すべてで割り切れないかどうかで判断します。
100 の二乗は 10000 なので、10000 以下の自然数の素数判定のために、51 以上 100 以下の範囲にある素数もまとめておきます。
【51 以上 100 以下の素数】
53, 59, 61, 67, 71, 73, 79, 83, 89, 97 が素数です。
全部で 10 個です。
10000 以下の自然数については、
これら 25 個の素数すべてで割り切れなければ、素数です。
素数判定法 :3ケタの自然数で素数判定
【自然数 a の素数判定】
まず、n2 ≧ a を満たす n を 1 つ見つける。
次に、n 以下のすべての素数が a を割り切るかどうかをチェックする。
a = 503 が素数かどうかを、この定理カスタムで確かめてみます。
232 = 529 ≧ 503 より、二乗して 503 以上の値となる n が 23 と見つかりました。
定理カスタムから、23 以下の素数すべてで、503 が割り切れるかどうかを確認することになります。
23 以下の素数は 2, 3, 5, 7, 11, 13, 17, 19, 23 です。
2 と 3 と 5 と 7 が 503 を割り切らないことは暗算で計算できます。
ですので、11 と 13 と 17 と 19 と 23 に絞って、503 を割り切るかどうかを確認することになります。
503 = 11 × 45 + 8,
503 = 13 × 38 + 9,
503 = 17 × 29 + 10,
503 = 19 × 26 + 9,
503 = 23 × 21 + 20
これで、503 は 23 以下のすべての素数で割り切れないことが確認できました。
定理カスタムから、503 は素数ということが分かりました。
157/191が約分できるか
157 / 191 について、分子と分母の公約数で 2 以上のものがあれば、約分できますが、どうでしょうか？
エラトステネスのふるいの応用で、分数が約分できるのかどうかです。
約分できなさそうと直観で思うことと、約分できないことを確定させることは大きな差となります。ここで、素数判定を定理カスタムで行います。
まず、分母から調べてみます。
142 = 196 ≧ 191 より、14 以下の素数は 2, 3, 5, 7, 11, 13 です。
191 は一の位を見ると奇数なので、奇数だから 2 で割り切れません。
したがって、3, 5, 7, 11, 13 について割り切れるかどうかを確認します。
191 = 3 × 63 + 2,
191 = 5 × 38 + 1,
191 = 7 × 27 + 2,
191 = 11 × 17 + 4,
191 = 13 × 14 + 9,
191 は 14 以下のすべての素数で割り切れなかったので、191 は素数です。
そのため、191 の正の約数は 1 と 191 のみです。分子の 157 は 191 より小さいので、191 では割り切れません。
よって、分子の 157 と分母の 191 の最大公約数が 1 なので、これ以上は約分できないということが分かりました。
定理カスタムで素数判定をすれば、おおもとの【定理】の素数判定をすべて終えていました。
そのため、おおもとの【定理】の証明を最後に書いておきます。この証明では、高校の数学で学習をする背理法を使います。
素数判定法 :根拠となる【定理】の証明
【定理】
k を 2 以上の自然数とし、
ルート k を越えない最大の整数を z とする。
このとき、z 以下のすべての素数で k が割り切れなかったとすると、k は素数である。
＜証明＞
この k が素数でないと仮定します。
すると、2 以上 k － 1 以下の範囲にある自然数 a, b が存在して、
k = ab と表すことができます。
仮定より a と b は z より大きい自然数なので、
k < (z + 1)(z + 1) ≦ ab = k となります。
つまり、k < k ということなので、矛盾です。
よって、背理法から k は素数ということになります。【証明完了】
注意点
今回の【定理】の証明で、その値を越えない最大の整数ということの意味が鍵となっていました。
この内容は、整数の問題で、たびたび出てくるので、論理的にまとめておきます。
整数 z が 実数 x を越えない最大の整数とすると、この定義から越えないわけですから z ≦ x ということになります。
ここで、z + 1 も整数です。大小関係について、
z + 1 > x, z + 1 = x,
z + 1 < x の 3 通りが考えられます。
しかし、z + 1 ≦ x とすると、
z < z + 1 ですから、z が x を越えない最大の整数ということに矛盾してしまいます。
そのため、必ず z + 1 > x となります。
よって、z が x を越えない最大の整数ということは、z ≦ x < z + 1 ということになります。
ちなみに、実数 x を越えない最大の整数のことを [x] と表すときがあります。この記号をガウス記号といいます。
この【定理】の内容ですが、与えられた自然数にルートをつけた数を小数で近似することを円滑に行うことが可能なときは、定理のまま素数判定をすれば良いわけです。
しかし、ルートをつけてからガウス記号をとることは、文系の方や中学生の方には重たいように思います。
そのため、ルートをつけてからガウス記号をとるということをしない表現で、素数判定を算数で行えるように今回のブログ記事を書いた次第です。
313 が素数かどうかを【定理】のまま判定するときには、「313 にルートをつけた数を越えない最大の整数以下のすべての素数」で 313 が割り切れるかどうかを確認します。
202 = 400 > 313 なので、
「20 以下のすべての素数全体」は「313 にルートをつけた数を越えない最大の整数以下のすべての素数全体」を含むことになります。
このちょっとした集合の考えで、「20 以下のすべての素数」について 313 が割り切れないということが確認できたら、【定理】の素数判定で述べられている素数についてすべて割り切れないということを確認したことになります。
調べる必要のない素数まで確認してしまうことが起きるときもありますが、1 万以下の自然数くらいだと大した差にならないです。
そのため、少し遠回りをすることで「ルートをつけてからガウス記号をとる」というハードルを回避できるというのが、今回のブログ記事の内容です。
今回の内容は、定理カスタムだとスムーズに算数的に使うことができました。
中国剰余定理という整数分野で出てくる発展的な定理も、証明は難しいですが、算数を通じて定理が示す内容に触れることができます。
リンク先のブログ記事で、算数の例から定理の使いを説明し、後半で厳密な証明を述べています。余りに関連した整数では、合同式を考えるとスムーズなときがあります。
そこで、合同方程式の解き方というブログ記事で、合同式を使った実践的な問題を解説しています。
また、最大公約数の求め方についても、手頃な大きさの例を用いて解説をしています。
さらに、n進数の小数という情報分野と数学の整数の内容が絡む記事も投稿しています。
それでは、これで今回のブログ記事を終了します。
読んで頂き、ありがとうございました。