暗算で素数判定(証明付き)
おはようございます。リユルンと申します。
さて、皆さんは時折 「この数、素数じゃないか」って疑いを持つことありますよね?(無いか、
まあこのnoteは素因数分解にでも利用して下さい)
例えば、第7世代(7も素数)、
USUMの発売年の2017年、
2017という数字は素数なんですよね。
また、発売日は11月17日、数字を横に並べた1117、これも素数です。
種族値が全て素数(アーゴヨンのS121は除く)なウルトラビーストが登場した世代ならではの特色だと感じてます。
目次的なもの
どこまで調べればいいの?
2の倍数か調べる方法
3の倍数か調べる方法
5の倍数か調べる方法
11の倍数か調べる方法
その他の倍数か調べる方法
おわりに
どこまで調べればいいの?
素数というのは、約数が1とその数自身の合計2つしか無い数です。
そのため、約数があると仮定すると、
素数判定したい数を素因数分解したときにa×b、という何かしらの式が出来上がりますよね。
このaはb以下の数と仮定できます。
(bの方を小さいと仮定しても、交換法則により関係ありません)
そうした時、bの部分までゴリ押しするよりも、aの部分までたどり着ければ、(1とその数以外の)約数を導き出せますよね。
そして、そのaとbの差が最も少なく、aが最も大きい数になるのはのは、aとbが同じ数の時です。
(例：121=11×11)
つまり、その数が 何と何の2乗の間にあるのかが導き出せれば、どこまで確認すればいいのかが分かるのです
例えば、2017は 50×50=2500、40×40=1600、45×45=2025…! と求めていけば、
43×43<2017<45×45 なので、
(完璧に証明するためには)43までの素数で割れるか否かを計算するだけになります
(44は元々素数ではなく、さすがに上の式から43×43<2017ということは分かるのでカットしてます)
あ、45×45も充分苦しそうですが、暗算で出来ますよ。この記事の終わりにでも計算方法を載せようと思います
2の倍数か調べる方法
1の位が偶数か、以上。
さすがに、証明はしなくていいですよね…
3の倍数か調べる方法
それぞれの位の数字を足して3の倍数→3の倍数です
例えば2017では2+0+1+7=10、
1117では1+1+1+7=10なので、どちらも素数ではありません
―以下(ラフではありますが)証明―
例えば 3桁の数字を式で表現してみると、
100a+10b+cとなります
100a=99a+a、10b=9b+bなので(これらを代入して)
99a+a+9b+b+c
=99a+9b+a+b+cと変換でき、
9でくくると
9(11a+b)+a+b+cとなります。
9は3の倍数なので、[a+b+c]が3の倍数なら
式全体を3でくくれる→3の倍数であることが確定
桁数が増えていっても、同じような式に出来ます。
(試しに1000dとか追加してみると 分かりやすいでしょう)
5の倍数か調べる方法
1の位が5か0か、以上。
これも さすがに証明しなくていいですよね…
11の倍数か調べる方法
[奇数行目の数字の和]と[偶数行目の数字の和]の差が0もしくは11の倍数→11の倍数です
例えば2017だと(0+7)-(2+1)=7-3=4、
1117だと(1+7)-(1+1)=8-2=6なので
どちらも11の倍数ではありません
―以下(ラフではありますが)証明―
例えば 4桁の数字を式で表現してみると、
1000a+100b+10c+d となります。
d以外を10でくくって
10(100a+10b+c)+d とします
次に、dより右の部分の係数を11にします。
そして それにより増えた分(100a+10b+c)を引いて均衡をとります。
11(100a+10b+c)-(100a+10b+c)+d…① と します。後で使います
そうして出てきた100a+10b+cは(実質符号が逆とはいえ)3桁の数字と表現できますよね。
つまり これを利用して3桁の数字の場合まで証明できます。
これも同じように、係数が11になるところを出した式にしていきます
100a+10b+c
=10(10a+b)+c
=11(10a+b)-(10a+b)+c…②
そうして出てきた10a+bは(実質符号が逆とはいえ)2桁の数字ですよね。
つまり(以下略)
ただ しここまで来ると10aを11a-aと表現するだけでよくなります。
10a+b
=(11a-a)+b…③
=11a-a+b、
分かりやすく変換すると11a-(a-b)
ここまでくれば、aとbの差が0もしくは11の倍数だと、式を全て11でくくれるようになるので 証明完了ですね
そしてこの式を3桁や4桁の時に代入すると同じように証明できます。
100a+10b+c (②より)
=11(10a+b)-(10a+b)+c (③より)
=11(10a+b)-(11a-a+b)+c
=11(10a+b)-11a+a-b+c…④
同じく 11の係数がかかっていないところに着目すると、符号が互い違いになっていますよね。
分かりやすく変換するとa+c-bになり、
奇数行目の和から偶数行目の和を引いています。
そしてこれが 0もしくは11の倍数だと、式全体を11でくくれるようになるので証明完了です。
もうお分かりかもしれませんが、4桁でも代入すると、
1000a+100b+10c+d (①より)
=11(100a+10b+c)-(100a+10b+c)+d (④より)
=11(100a+10b+c)-(11(10a+b)-11a+a-b+c)+d
(11でくくれる箇所が見つかるので)
=11(100a+10b+c)-(11(10a+b-a)+a-b+c)+d
=11(100a+10b+c)-11(9a+b)-a+b-c+d
この式が出せ、同じく 係数が11の箇所以外は符号が互い違いになる箇所が現れたので、これで証明できましたね
2桁→3桁、3桁→4桁になっても同じことが繰り返されたので、5桁、6桁、7桁…と増えていっても同じです
その他の倍数か調べる方法
自然数nについて 特定の数(以下m)の倍数かどうかだけなら 楽に求める方法があります。
自然数nの mで割ったときの余りが0(つまりmの倍数)なら、
nからmの倍数を増減させても、
またmの倍数からnを増減させても 余りは0のままです。
以下(ラフではありますが)証明
ここでは特定の数、mを ひとまず13と仮定します。(その他に数字が出てこないので もうこれでいいと思われます)
すると自然数nは
n=13x+d
(↑紛らわしいけどエックスです)と表せます。そしてdが0の時のみ nは13の倍数です。
13×7である数、91を引いてみるとします。
すると式は13x+d-13×7、
dだけ放っておいて13でくくれますので
13(x-7)+dとなり、d、つまり余りは変わりません
91を足してみても、符号が入れ替わるだけなので同じく13の倍数であることに変わりはありません。
逆に 91からnを引くパターンでも、
13×7-(13x+d)
=13×7-13x-d
=13(7-x)-dとなり、
dが0→元々の数が13の倍数なら、13の倍数であることに変わりません
（dが0以外なら 余りは(0以外に)変わりえますが）
証明終了
この仕組みを利用して、だんだん簡単な数に変化させていくのです
ではこの仕組みを使って2017が7で割れるか判定してみましょう
7×300の2100から2017を引くと83、
7×14は84…あ、
はい、7の倍数ではありません。
1117も同じく、1117から(7×100の)700を引いて417、
その417から(7×50の)350を引いて67、
7×9は63…
はい、7の倍数ではありません。
ただ、この方法は23みたいに 特定の数が大きい時や、調べたい数が(ウルトラビーストの種族値みたいに)比較的小さい時は そのまま割り算した方が早い場合があります。
おわりに
ここまでお付き合いいただき、ありがとうございました。
11の倍数か調べる方法や その他の倍数か調べる方法は、実は私も調べて初めて知ったので 勉強になりました。
(一応7の倍数かどうか調べる方法もあるのですが、↓
https://twitter.com/riyulun/status/1384083009335222272?s=19
「普通に7で割った方が早くない?」と感じたのでカットしました)
面白かった方は 是非スキをお願いします。
Twitter→ https://twitter.com/riyulun?s=09
最後に 参考までに100までの素数と45 ×45 の際にした工夫を載せて 終わりとさせていただきます
100までの素数
2、3、5、7、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97
45×45の工夫
45は9×5なので、全体を45×9×5に出来ます
9は10-1なので、
45×9=45×(10-1)
=450-45=405と求められ、
あとは5をかけて 405×5=2025です