1

素数判定公式

107
0
$$$$

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

$$\normalsize{N_{10} }\equiv 判定したい任意の10進数 $$
$$\normalsize{n} \equiv\lbrace 2,3,4 \cdots \normalsize{n}\vert n \in \mathbb{N} ,n \geq 2 \rbrace で表わされる進数 $$
$$\normalsize{h} \equiv \lbrack \sqrt{N_{10} } \rbrack ※記号が見つかりませんでしたので[]としましたが、 $$ $$床関数です。以後[]は床関数の意味です。 $$
$$\normalsize{m} \equiv \lbrack \sqrt{N_{10} -1} \rbrack $$
$$ {}^{n} P \equiv 判定結果として返される値 $$
$$\normalsize{P} \equiv 素数 $$以上を用いて判定公式を示します。
$${}^{n} P \equiv (\sum_{n=2}^{h} \lbrack \frac{N_{10} -n}{n} \rbrack)- (\sum_{n=2}^{m} \lbrack \frac{(N_{10} -1)-n}{n} \rbrack) $$
$${}^{n} P \equiv 0 \Rightarrow N_{10} \equiv P $$
$${}^{n} P \equiv 1 \Rightarrow N_{10} \equiv P^{2} $$
$${}^{n} P \geq 2 \Rightarrow N_{10} \equiv 合成数 $$
$$P^{2} も合成数なので {}^{n} P \equiv 0 と {}^{n} P \neq 0で分ければよい。 $$

上記のようになる理由

§1

$\boldsymbol{n}$進法で書かれた数を10進法にするには
$$\boldsymbol{a}を10進法の各桁の数、 \boldsymbol{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であることが
$$ \boldsymbol{n}進法で書かれた数の末尾が0になる条件である。 $$$a_{0}$$n_{0}$以外の項はすべて$\boldsymbol{n}$を因数に持つことは明らか。

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

§2

投稿日:2023320
更新日:-1秒前

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中