↓↓↓動画で見たい方はこちら↓↓↓

素数とは

素数（そすう）とは1と自分自身以外の約数を持たない2以上の整数のことです。少し言い換えると、素数とは「約数が2つしかない自然数」や「1と自分自身以外の自然数で割り切れない1以外の自然数」といえます。（今回は約数を正の約数の意味で使います。）
例としては、小さい方から並べていくと2,3,5,7,11,…のような数のことです。実際、これらの数の約数を見ていくと、2の約数は1と2、3の約数は1と3、5の約数は1と5、…のように約数は2つのみです。逆に4や6などは、それぞれ約数が1,2,4と1,2,3,6となり2個以上になるので素数ではありません。また、1以外の素数でない数は合成数と呼びます。

素数の見分け方その1

素数の見分け方は大きく分けて2つの調べ方があります。
1つ目は素数か判定したい整数が何かの数の倍数になっているかどうかを調べる方法です。もし、この段階で何かの数の倍数になっているとわかればその数で割り切れることになるので、素数ではないとわかります。
この考え方を使うと、2の倍数である偶数は2を除いてすべて素数ではないとわかります。
このときに知っておくと便利なのが倍数の判定法です．例えば、1の位が0,2,4,6,8のどれかであれば、2の倍数であることがわかります。
他の数にも大きな数などを単純に割って調べるよりも早く倍数かどうかを判定できる方法があります。

素数の見つけ方その2

2つ目は2から順番に約数になるかを総当たりでチェックする方法です。
これは単純に約数かどうかを総当たりで調べるというだけです。
ここでnという整数が素数か判定するときに、ただ単に2からn-1まで総当たりで調べるのではなく、実は、2から\(\lfloor\sqrt{n}\rfloor\)（nを超えない最大の整数）まで調べればいいことが約数の性質からわかります。
素数かどうかを判定するときには基本的にはこの2つの方法を使って調べていきます。
素数は紀元前の頃からユークリッドなどによって研究されており、有名なものでは、エラトステネスの篩（ふるい）と呼ばれる素数の見つけ方が考えられていました。

素数の活用

素数はこの素朴な定義（言葉の意味付け）からは想像できないほど深い背景を持っています。
素数の見分け方がとても手間がかかるものだと感じた方いるかもしれませんが、それは素数が不規則に現れ、効率的に見つけるのが難しいからなのです。
しかし、その見つけることの困難さが現代では私たちのデータを守る暗号として利用されるなど、私たちの生活に欠かせないものとなっています。

●和からのセミナー一覧はこちら
●お問い合わせフォームはこちら

公倍数と公約数とは【算数からやさしく解説】

<文/尾崎>

14歳からのニュートン超絵解本 素数　ニュートン編集部(著,編)　ニュートンプレス