➗素数判定

素数とは

素数とは、1とその数自身以外に約数を持たない2以上の整数のことです。2・3・5・7・11のような数が素数で、2は偶数の中で唯一の素数です。

1は素数か

1は素数ではありません。素数は2以上の整数と定義されており、1を素数に含めると「どの整数も素数の掛け算でただ1通りに表せる」という素因数分解の性質が成り立たなくなるためです。

素数の見分け方

整数nが素数かどうかは、√n以下の数で順に割り、どれでも割り切れなければ素数と判断できます。たとえば91は√91（約9.5）以下の7で割り切れるため素数ではありません。

• 試し割り法：試し割り法は、2から√nまでの数でnを順に割って約数を探す方法で、桁が大きくなると割る回数が膨大になります。
• ミラー・ラビン判定法：ミラー・ラビン判定法は、いくつかの数を「底」として累乗の余りを調べ、素数でない証拠を見つける方法で、大きな数でも短時間で判定できます。