素数判定の試し割り法 エラトステネスの篩とは

どうも、木村(@kimu3_slime)です。

今回は、素数かどうかの判定法として、エラトステネスの篩を紹介します。

 

エラトステネスの篩とは

素数とは、1とそれ自身以外に約数を持たない数のことでした。素数ではない数を合成数と呼びます。

つまり、\(2\)で割り切れる\(2\)以外の数は素数ではありませんし、\(3\)で割り切れる\(3\)以外の数は素数ではありません。小さな数で割りきれる数(合成数)をはじいていくことで素数を見つける方法は、エラトステネスの篩(ふるい)(sieve of Eratosthenes)として知られるものです。エラトステネスは、古代ギリシャの数学者です)

\(50\)以下の整数について、エラトステネスの篩にかけてみましょう。まず、数を並べて、2で割り切れる数を消していきます。

さらに、3の倍数を消します。素数でない数、合成数をふるいおとしているようすがわかりますね。

5の倍数を消します。かなり減ってきました。

7の倍数を消します。

割る数となった最初の数\(2,3,5,7\)は素数です。そして、残った数\(11,13,17,19\),\(23,29,31,37\),\(41,43,47\)が素数の候補になります。実は、候補であるだけでなく、実際にこの方法では、\(7^2=49\)以下の素数が見つけられるのです。

 

素数の判定法

与えられた整数\(x\)が素数かどうかは、「ある程度小さな」素数すべてによって割り切れるかどうかで判定できます。

\(x\)を2以上の整数とする。\(\sqrt{x}\)以下のすべての素数\(p\)(\(p \leq \sqrt{x}\))で割り切れないなら、\(x\)は素数である。

対偶を示しましょう。\(x\)が合成数ならば、\(x\)は\(p \leq \sqrt{x}\)を満たすある素数\(p\)で割り切れることを示します。

\(x\)を合成数(素数でない)と仮定します。\(1\)でも\(x\)でもない約数を持つので、\(x=ab\)、\(2\leq a <x\)、\(2\leq b <x\)を満たす整数\(a,b\)が存在します。\(a\)は2以上の整数なので、素因数分解したときに少なくともひとつの素数を含みます。つまり、\(a=p_1 p_2 \cdots p_N\)と表せます(算術の基本定理)。\(p=p_1\)と置きましょう。\(p\)は素数であり、\(a\)を割り切り\(p \mid a\)、したがって\(p\)は\(x\)も割り切ります。また、\(p \leq p_1 p_2 \cdots p_N= a \leq \sqrt{x}\)が成り立ちます。なぜなら、\(a\leq b\)のとき、\(a^2 \leq ab =x\)でルートを取れば良いからです(\(a\geq b\)でも、\(b\)を素因数分解して同様に議論できる)。よって、\(x\)を割り切る素数\(p\)で、\(p \leq \sqrt{x}\)を満たすものが存在することが示せました。

 

この判定法は、エラトステネスの篩の原理です。\(10=\sqrt{100}\)以下の素数は、\(2,3,5,7\)と知っているとしましょう。そして、数\(x\)を\(2,3,5,7\)で割ってみて、割り切れない数を考えます。その数は、さきほど示したことにより素数であると言えるわけです。図としては\(50\)までしか書きませんでしたが、\(7\)で割り切れるかチェックした時点で、\(100\)以下の素数を見つけられます。

 

\(x\)が素数かどうか判定するために、\(x\)以下のすべての素数で割りきれるかどうか試さなくても、\(\sqrt{x}\)以下の素数を調べれば良い、というわけです。

\(151\)が素数かどうか判定してみましょう。\(12 \leq \sqrt{151} < 13\)なので、\(11\)までの素数で割り切れるか調べれば十分です。\(2,3,5\)で割り切れないのは良いでしょう。\(140+11\)なので\(7\)で割り切れません。\(110+41\)なので\(11\)でも割り切れません。よって、\(151\)は素数です。

ルートの不等式について:ルートの近似値の求め方 不等式を使って大小比較

\(2021\)が素数であるかどうか判定してみましょう。\(40 \leq \sqrt{2021} \leq   50\)なので、\(50\)以下の素数で割り切れるか調べれば十分です。ちょっと多いですが、上で得た\(50\)以下の素数の表を使って、地道にやってみましょう。

\(2\)では割り切れません。\(1800+221\)なので、\(3\)で割り切れません。\(2100-79\)なので、\(7\)で割り切れません。\(2200-179\)なので、\(11\)で割り切れません。\(1300+650+71\)なので、\(13\)で割り切れません。\(1700+340-19\)なので、\(17\)で割り切れません。\(1900+95+26\)なので、\(19\)で割り切れません。\(2300-230-49\)なので、\(23\)で割り切れません。\(29*70-9\)なので、\(29\)で割り切れません。\(1860+161\)なので、\(31\)で割り切れません。\(2220-99\)なので、\(37\)で割り切れません。\(2050-29\)なので、\(41\)で割り切れません。

……ところが、\(43 \cdot 47=2021\)と割り切れてしまいます。つまり、\(2021\)は素数でないことがわかりました。

より大きな数になると、手計算ではかなりしんどくなりそうですね。コンピュータで計算するにしても、素数判定には工夫が必要となってくることがわかります。

 

以上、素数かどうかの判定法として、エラトステネスの篩を紹介してきました。

3桁や4桁くらいまでの数なら、この方法で手計算してチェックできるので、町中で出会った数に対して素数かどうか判定してみてください。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

Elementary Number Theory

Elementary Number Theory

posted with AmaQuick at 2021.02.16
Burton(著)
(2012T)
4.6outof5stars
¥5,437

 

はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで
Joseph H. Silverman(著), 鈴木 治郎(翻訳)
丸善出版 (2014-05-13T00:00:01Z)
4.4outof5stars
¥3,740

 

こちらもおすすめ

素数の性質:無限にあること、素因数分解の一意性と応用

「AならばB」証明の書き方、直接法、対偶法、背理法

整数の除法、割り切れる・約数b|a、最大公約数gcdとは?

ルートの近似値の求め方 不等式を使って大小比較