素数とは

中3数学数論中3数学




目次
  • 1. ①素数の定義と例
  • 2. ②素因数分解
  • 3. ③素数の判定方法
  • 4. ④エラトステネスの篩(ふるい)

①素数の定義と例

まずは、素数の定義について確認しておきましょう。

素数の定義

自然数で\( 1 \)とその数自身の他に、約数を持たない数を素数という。

つまり、約数が2つである自然数のことを素数という。例を挙げておくと、

2・・・1と2(自分自身)でしか割れないので素数。
3・・・1と3(自分自身)でしか割れないので素数。
4・・・1と4(自分自身)以外にも2で割れてしまうので素数ではない。
5・・・1と5(自分自身)でしか割れないので素数。
6・・・1と6(自分自身)以外にも2や3で割れてしまうので素数ではない。

ここで出てきた4や6のように、素数以外の自然数のことを合成数といいます。


②素因数分解

合成数は素因数分解により、素数の積で表すことができる。

18を素因数分解する。

18は、2という素数で割ることができる。
すると、\( 18 \div 2=9 \)より、9が残る。

その9は、3という素数で割ることができる。
すると、\( 9 \div 3=3 \)より、3が残る。

3は、3という素数で割ることができる。
すると、\( 3 \div 3=1 \)より、1が残る。

こうして、1が出てきたら、筆算終了。今までに割った数が素因数分解の結果である。
\begin{equation}
18=2 \times 3^2
\end{equation}

素因数分解の結果は、素数をかける順序を考慮しなければ、分解は一意に決まります。
 
しかし、1を素数としてしまうと、
\begin{align}
18&=2 \times 3^2\times 1 \\
&= 2 \times 3^2\times 1^2 \\
&=2 \times 3^2\times 1^5
\end{align}
のように、一意ではなくなってしまうため、素因数分解の一意性を保持するために、1は素数としません。


③素数の判定方法

ある自然数が与えられたとき、その自然数が素数かどうかを判定するためにはどのような作業をすればよいか?その判定法について、下にまとめてみた。

素数の判定方法

ある自然数\( N~\) が素数かどうかを判定するためには、\( [\sqrt{N}]~\) までの全て素数で\( N \)が割り切れるかどうかを確かめ、割り切れる素数が無いとき、\( N~\) は素数であると言える。
ただし、\( [\sqrt{N}]~\) は\( N ~\) を超えない最大の整数。

要は、調べたい自然数の平方根以下の全ての素数で割ってみて、割れたら合成数、割れるものが無ければ素数ということです。下の例で実際にやってみます。

例1

103が素数かどうかを調べる。

\( 10 < \sqrt{103} < 11~\) より、\( [\sqrt{103}]=10~\) である。よって、10以下の素数で割れるかどうかを調べてみる。
\begin{align}
& 103\div2=51\cdots 1 \\
& 103\div3=34\cdots 1 \\
& 103\div5=20\cdots 3 \\
& 103\div7=14\cdots 5 \\
\end{align}
割り切れる素数が無かったため、221は素数である。

例2

221が素数かどうかを調べる。

\( 14 < \sqrt{221} < 15~\) より、\( [\sqrt{221}]=14~\) である。よって、14以下の素数で割れるかどうかを調べてみる。
\begin{align}
& 221\div2=110\cdots 1 \\
& 221\div3=73\cdots 2 \\
& 221\div5=44\cdots 1 \\
& 221\div7=31\cdots 4 \\
& 221\div11=20\cdots 1 \\
& 221\div13=17  \\
\end{align}
13で割り切れるため、221は素数ではない。ちなみに素因数分解をすると、\( 221=13\times17~\) である。

このサイトの素数判定プログラム(→素数判定のページへ)は、上記の考え方を使っています。ある自然数の平方根以下の素数だけを確かめるということが、プログラムのスピードを上げています。
 
なぜ、平方根以下の素数だけでいいかというと、先ほどの例2からわかるように、与えられた自然数の平方根以上の素数を確かめる前に、与えられた自然数の平方根以下の数で割れてしまうからです。
つまり、221を17で割るよりも前に、221は13で割れてしまうため、平方根以上の素数については確かめる必要が無いということになります。


④エラトステネスの篩(ふるい)

有名な素数の見つけ方として、エラトステネスの篩(Eratosthenes’ sieve)という方法があります。これは、1つ1つの素数を調べるのではなくて、ある程度まとまった単位で調べることができる方法です。次の例で、その方法について見ていきます。

1から100までの素数を全て求める。

まず前提条件として、\(  \sqrt{100} =10~\) より、\( [10]=10~\) なので、10以下の素数だけを調べればよい。
100までの数を下図のような表にする。
(1)1は素数ではないので、初めに消しておく。
(2)2の倍数を消す。
2の倍数は縦に並んでいるため、2以外の2の倍数を全て消すと、下図のようになる。
(3)3の倍数を消す。
3の倍数は斜めに並んでいる。3以外の3の倍数を全て消すと、下図のようになる。
(4)5の倍数を消す。
5の倍数は縦に並んでいる。5以外の5の倍数を全て消すと、下図のようになる。

(5)7の倍数を消す。
7の倍数は斜めに並んでいる。7以外の7の倍数を全て消すと、下図のようになる。

以上より、残った素数は次の25個である。


素数判定のプログラム、最初は与えられた自然数より小さい素数を全て割ろうとプログラムを組んだものの、8ケタくらいでフリーズ・・・。割る試行は平方根以下の素数までに改良した結果、16ケタくらいまでは速攻で計算してくれるようになりました。数学を理解することは大切ですな。

   
 
 


☆参考文献等
・吉田武(2010)『新装版 オイラーの贈り物-人類の至宝\( e^{i \pi}=-1 \)を学ぶ』東海大学出版会

中3数学数論中3数学

Posted by Fuku