素数判定公式（なぜそうなるかの解説付き）※

以下の式により素数か素数でないかの判定が可能です。
なぜこの式で判定できるのか、合間を見つけて少しずつ投稿していく予定
まずは計算サイトなどで様々な素数を代入してみてください。
どんな大きな素数にも確実に反応します。素数でない数も的確に返します。
ぞろ目の非素数にもしっかり反応します。
ｎについては10進数の数列でもよいのですが、ｎ進数とした方が美しくなりますのでそちらを採用させていただいております。
まずは使用する記号を記します。

$$N_{10}\equiv 判定したい任意の10進数$$
$$n\equiv \{2,3,4\cdots n|n\in \mathbb{N},n\ge 2\}で表わされる進数$$
$$h\equiv ⌞\sqrt{N_{10}}⌟・・・(a)$$ $$※ ⌞⌟は床関数$$
$$m\equiv ⌞\sqrt{N_{10}-1}⌟・・・(b)$$
$${}^{n}P\equiv 判定結果として返される値$$
$$P\equiv 素数$$以上を用いて判定公式を示します。
$${}^{n}P\equiv (\sum _{n=2}^h⌞\frac{N_{10}-n}{n}⌟)-(\sum _{n=2}^m⌞\frac{(N_{10}-1)-n}{n}⌟)・・・(c)$$
$${}^{n}P\equiv 0\Rightarrow N_{10}\equiv P$$
$${}^{n}P\equiv 1\Rightarrow N_{10}\equiv P^2$$
$${}^{n}P\ge 2\Rightarrow N_{10}\equiv 合成数$$
$$P^2も合成数なので{}^{n}P\equiv 0と{}^{n}P\ne 0で分ければよい。$$

上記のようになる理由

§1

$\mathit{n}$進法で書かれた数を１０進法にするには
$$\mathit{a}を10進法の各桁の数、\mathit{k}を桁数とすれば$$ $$a_n{n}^k+a_{n-1}{n}^{k-1}+\cdot \cdot \cdot +a_1{n}^1+a_0{n}^0$$ となる。$n^0$は1であるので$a_0$$=$0であることが
$$\mathit{n}進法で書かれた数の末尾が0になる条件である。$$※$a_0$$n_0$以外の項はすべて$\mathit{n}$を因数に持つことは明らか。

$a_0$$n^0$が0になるためには
10進法で書かれた数が$\mathit{n}$で割り切れればよい。
即ちこのことは$a_0$$n^0$の項を消すことで上記※に記したように
10進法で書かれた数が、少なくとも$\mathit{n}$を約数にもつことになる。
$\therefore$$\mathit{n}$進法で書かれた末尾0の数は素数ではない。
といえる。

§2

ここからは、下記の表を参照しながら進めてゆきます。

末尾0を除外する範囲について

$$\mathit{ｎ}進数で表わされる特定の数をN_n例えば３進数で110などをN_3=110と表わすとすれば$$
全ての末尾0は以下のように指定できる。
※当然のことのように思われると思うが必要な部分です。

$$N_n\cdot \frac{N_{10}}{N_n}=N_{10}$$
例えば3進数で10進数の12を表している時3進数は110、この110は3進数において末尾0として4つ目に現れる数です。この個数4に3進数の3をかけることによって10進数の12が表せるということ。
いくつ目に現れる末尾0かということを$\acute{n}$で表わすとすると（※以下、図1を参照しながら確認ください）

$$N_n\cdot \acute{n}=N_{10}$$となる、このことは10進数の12は3進数の4番目の末尾0でも表せるし、4進数の3番目の末尾0でも表せることになる（※10進数の12に関しては他にもペアが存在するがここでは割愛する）即ち合成数において（ゾロ目以外）すべて上記のようなペアが存在する。このことを末尾0の最初の数である10に当てはめて考えてみる。10は1つ目に現れる末尾0であることは自明であるので、ペアの片方では必ず1進数が必要になってしまう。1進数において末尾0は存在しないので、ペアが構成できない。ペアができないことは合成数と確定できないことを意味する。なぜなら1×任意の進数で表わされるものは素数である要件を満たす（任意の進数が素数である場合）ことになるし、表わされるのはその進数自身であり、すべての自然数を示すことができてしまうからである。
以上の理由より末尾0のうち、最初に現れる10は除外して考えることとする。

末尾0を調べればよい範囲

末尾0のうち、100は特別な数である。これはぞろ目を意味する。ここでいうぞろ目は例えば
$N_{10}$$=$${\left(\sqrt{N_{10}}\right)}^2$
となっている数のことである。
例えば$N_{10}=$49がこれに相当する。
図1　を参照いただきたい。赤く示したラインが100ラインである。先ほど末尾0のうち10は除外して考えることを示した。したがって10を除いた末尾0には図中分かり易くするために黄色で塗りつぶしてある。
見ていただければわかると思うが黄色のセルの数は各行（横の並び）
100ラインで左右に分けると、どの行も左右同数であることがわかる。
先述で、各進数10を境にペアが存在すると記した。同様に各進数100を境にペアが存在する。図1を参照していただいて。例えば$N_{10}$$=$24をみてみると100の赤いラインを境に以下の表のようになる。

100ラインは４進数と６進数の間に存在するので、それぞれ２進数の12個目と12進数の２個目、３進数の8個目と8進数の3個目、4進数の6個目と6進数の4個目でペアができる。結局それらはすべて10進数の24を示しているので100ラインを境に重複表示しているといえる。
進数と～個目とそれぞれの示すものは違うが、これはあくまで数字の数え方の単位のようなもの、実質やっているのは単純な掛け算であるので
$$a_1\cdot b_1\iff b_1\cdot a_1$$
$a_2$$\cdot$$b_2$$\iff$$b_2$$\cdot$$a_2$
$$a_3\cdot b_3\iff b_3\cdot a_3$$
ということである。

各進数×～個目は約数の積である。約数の積は$n^2$を境に重複で現れる。
もう一つ表を参照いただきたい。

表中＾2セルを境に同じ積がペアで表れている。
このことを具体的に$N_{10}$$=$12の約数の積でみてみよう。
｛表3｝

＾2のセルの並びを境に同じペアが2個づつ存在していることがわかる。

§3

この素数判定公式でやりたいことは、10進数で表わされたある数$N_{10}$が、素数かそれとも合成数かの判定である。
§2で見てきたことを踏まえて考えてゆく。
$$N_{10}の約数として調べる必要のある最大の進数を\mathit{n}とすれば$$ $\mathit{n}$$\leqq$$N_{10}$
更に重複を考慮に入れると
$$\mathit{n}\leqq ⌞\sqrt{N_{10}}⌟・・・（1）$$
先の$N_{10}$$=$12を例にした表をご照覧あれ。
表の横軸を進数、縦軸を個数として考えると（1）によれば、
この表中$\mathit{n}$$=$3まで且つ、その左側に存在する12を考慮に入れれば事足りるということになる。1進数は§2で除外したので$\mathit{n}$$=$2,3のみを考慮に入れればよい。＾2ラインを境に重複が生じているのでこのラインより右に約数が存在しているか否かはもはや問題ではない、なぜならその領域に約数が存在すれば必ずペアとして左側領域にも出現するからである。そして素数か合成すかを判定するにあたって、すべての約数をカウントする必要はない、なぜなら1とその数自身に一つでも約数が存在するならばそれは素数でなく合成数であると判定できるからである。

§3

§2までで、調べる範囲と除外する範囲を指定した。このセクションでは冒頭で既出の式(b)の各パーツについてその意味を示してゆく。
再度式（b)を記載する。
$${}^{n}P=(\sum _{n=2}^h⌞\frac{N_{10}-\mathit{n}}{n}⌟)-(\sum _{n=2}^m⌞\frac{(N_{10}-1)-\mathit{n}}{n}⌟)$$
$$\mathit{h}=⌞\sqrt{N_{10}}⌟・・・(Re1)$$
$\mathit{m}$$=$$⌞$$\sqrt{N_{10}-1}$$⌟$
※$⌞$$⌟$は床関数

準備は整ったので本題に入ります。
各進数で末尾0が現れる頻度は２進数なら２個に１つ、3進数なら３個に1つである、そしてこの後の数も同じであることは自明である。
任意の10進数$N_{10}$までに任意の進数$\mathit{n}$の末尾0がいくつ存在するかは、したがって
$$\frac{N_{10}}{n}・・・(d)$$で表わすことができる。
各進数最初の末尾0である10は§２で定めた除外範囲に該当するのでこのカウントから除外しなければならない。この操作は(d)式の分子を
$$N_{10}-\mathit{n}・・・(e)$$と置き換えればよい。よって
$$\frac{N_{10}-n}{n}・・・(f)$$
(f)式は図1でいえば任意の進数の黄色のセルの個数の縦計である。
任意の$N_{10}$について素数か否かを調べたいとき、その１０進数の数において§2で示した範囲内で末尾0が存在するか否かを確認し、存在すれば素数ではないし存在しなければ素数であると判定できる。ここで確認するが、末尾0を調べることは任意の$N_{10}$の全ての因数を調べていることになる｛表2｝（※§2で掲示した２つ目の表）を参照。表は$N_{10}$$=$12について調べているが＾2セルの斜めの並びの左側に存在する12のセルは2つあり、それぞれ3・4と2・6を示す、この4つは1と12を除けば12のすべての因数である。
さて、では§2で示した範囲内で任意の$N_{10}$までの範囲にに存在する末尾0を総計することとする。§2で指定した調べる範囲は(Re1)で示した$\mathit{h}$である。$\mathit{h}$は調べる必要のある$\mathit{n}$の範囲の上限である。下限は2であるので式としては
$$\sum _{n=2}^h\frac{N_{10}-n}{n}・・・(g)$$ となる。
素数は1と自身以外には約数を持たないのであるから、任意の進数での特定の数を$n_kとすれば$$$$$$N_{10}$$⟹$${}^{n}P$$⟺$$n_k$$\ne$末尾0

少し具体的に見てゆこうと思う。図1を再度参照いただいて、任意の$N_{10}$の行を横に追ってゆくと素数の行には黄色のセルは存在しない、素数でない数の行には必ず黄色のセルが存在する、さらに言えば行のうち調べる必要のある範囲内に黄色のセルが必ず存在する。

最後の仕上げです。
(c)の等式（これが素数判定公式なのですが）の右辺第１項は説明が終わった。続いて第２項について述べるのだが、ここで素数判定公式の判定方法について述べる、なぜかといえばこれがわかれば第２項は説明さえいらない程度に容易に理解できるからである。

素数判定公式の素数判定方法について（第2項の説明も兼ねる）

任意$N_{10}$が素数であった場合、どの進数で表しても末尾0にはならない。
であるならば、（図1）のように表にした場合、素数である$N_{10}$を横軸にたどっていってもそこに末尾0は一つもないのであるから、黄色く塗りつぶしたセルは一つもないということになる。ここでは見る範囲を少なくするために$N_{10}$$=$11を判定してみる。右辺第1項で行ったのは11より上であり、ぞろ目ライン（図中赤いラインと、100のセルで表されている。100は赤く塗りつぶしたセルであるが、これは視覚的に分かり易くするためであり、末尾0ということに変わりはないので黄色のセル同様である）より左側にある２進数の100，110，1000，1010と3進数の100のセルを全て数えることであった。
11が素数であることは疑いなく、当然11の横軸に黄色のセルは一つもない、
であるならば同様の範囲の$N_{10}$$=$10までの黄色のセルの個数の合計と$N_{10}$$=$11までの黄色のセルの個数の合計は全く同じはずである。
つまり素数か否か判定したい１０進数の任意の数とそのひとつ前の数の黄色のセルの個数の合計を調べ、差をとると答えが０となるものは素数であると判別できるし、０以外となるものは（その数の横軸に黄色のセルが存在するということになるので）素数でないと判定できる。更に、答えが１となるものは自身と１以外に一つしか約数を持たない数、そのような数は7×7＝49や11×11＝121などのぞろ目であるとわかる。
以上が素数判定公式の考え方である。
従って右辺第2項は、第１項の一つ前までの数について第1項と同じく既定の範囲内で末尾0であるセルの個数を総和したものである。
第１項と第2項の差をとることにより判定は完了する。

視覚的な解説になってしまいましたが以上が素数判定公式の考え方です。
末尾0を調べることは、すべての因数について調べることと同値であることは先にも述べましたが、すべての因数を調べ、それを内包する末尾0の総和を用いた判定法に漏れや、数が大きくなると例外が出てくるということは帰納法的な観点からないといえます。