女性向けエンジニアスクール
3秒でわかる
1 と自分自身以外に約数を持たない 2 以上の整数。整数の分解の基本単位であり、暗号や試験問題のアルゴリズム題材として登場します。
もう少し詳しく
どういうものか
素数は、2 以上の整数のうち、1 と自分自身以外の約数を持たないものです。2、3、5、7、11 と続き、2 だけが偶数の素数です。1 は素数に含めません。含めてしまうと、任意の整数を素数の積として表す方法が 1 通りに定まらなくなるためです。
すべての整数は素数の積として、順番の違いを除いてただ 1 通りに分解できます。この性質のため、素数は整数の世界の基本部品として扱われます。
なぜ必要か
プログラミングの学習では、素数判定は繰り返しと条件分岐、そして計算量の考え方をまとめて練習できる題材として頻繁に出てきます。試験でも定番です。
実務に直結する面もあります。公開鍵暗号の RSA は、大きな素数を 2 つ掛けるのは簡単でも、その積から元の素数を求めるのが極めて難しい、という差の上に成り立っています。ハッシュ表の大きさに素数を選ぶ実装があるのも、偏りを減らすためです。
具体例
素朴な判定と、平方根までで打ち切る改良版です。
def is_prime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
i = 3
while i * i <= n: # 平方根まで見れば十分
if n % i == 0:
return False
i += 2 # 奇数だけ試す
return True
print([n for n in range(2, 30) if is_prime(n)])一定範囲の素数をまとめて欲しいときは、倍数を消していくエラトステネスの篩のほうが速くなります。
つまずきやすいところ
n までの全部の数で割る実装を書くと、桁が増えたときに終わらなくなります。約数は平方根を境に対になって現れるため、平方根を超える範囲を調べる意味はありません。この一手間で、計算量は n に比例する形から、その平方根に比例する形へ落ちます。
境界の扱いも間違えやすい箇所です。0 と 1 を素数と判定してしまう実装、2 を除外してしまう実装がよく出ます。書いたら 0、1、2、3、4 の 5 つを必ず通してください。
平方根の比較を i * i <= n ではなく浮動小数の平方根で書くと、大きな値で誤差により判定がずれることがあります。
覚え方
素数は「それ以上ばらせない数」です。合成数は必ず素数の積に分解できますが、素数はそこで止まります。整数を分解していったときの、いちばん下の部品が素数だと捉えると、暗号や試験問題で問われる性質もつながって見えてきます。
