【Python】素数を見つけるアルゴリズムと効率的な探索

こんにちは新米太郎です！

今回は素数判定のプログラムについて解説します。
素数を判断する原理と、より効率的な探索について考えて行きます。

数学的な用語は極力使わずに、アルゴリズムの考え方を説明することを心がけたので
数学が苦手な方でも読んでいただけると思います！

素数とは
素数の判定方法
プログラムを書くときの考え方
100までループさせて素数を見つける
探索条件について考える
最後に

素数とは

素数（そすう、英: prime number）とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

つまり、1とその数以外に約数がない数字のことです。

言葉だけ聞くと少し難しく聞こえますが
実際の数字で考えるとわかり易いです。

例えば「3」と「5」
3は1と3以外、5は1と5以外では割り切れないので素数です。
2や7も同様です。

6はどうでしょうか？
2で割れてしまうので素数ではありません。

ちなみに素数を並べると下のように大量にあります。

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149…

素数の判定方法

1とその数だけで割れること（約数が2個）なことを確かめれば見つけらます

5の場合
5 ÷ 1 　割りきれる
5 ÷ 2 　割りきれない
5 ÷ 3 　割りきれない
5 ÷ 4 　割りきれない
5 ÷ 5 　割りきれる
約数が1と5だけなので素数

6の場合
6 ÷ 1 　割りきれる
6 ÷ 2 　割りきれる
6 ÷ 3 　割りきれる
6 ÷ 4 　割りきれない
6 ÷ 5 　割りきれない
6 ÷ 6 　割りきれる
約数が1,2,3,6なので素数でない

これらを踏まえると
2以上N-1の間で割りけれなければ素数だと分かりますね。

プログラムを書くときの考え方

先ほどの「6」で考えると
2～5で割切れたら素数でないと判断できるので、それをプログラムとして書いてみます。

num = 6　　　　#判定する数字
str = "素数"

for i in range(2,num):
if num % i == 0:　　　　# iで割り切れるか
str = "素数でない"　　# iで割り切れた場合は素数ではない
break

print(str)

numの数字を2からnum-1まで割って、割り切れた場合には素数としています。
numの値を変えて色々試してみてください。

100までループさせて素数を見つける

MAX = 100 # 探索する最大値
for num in range(2,MAX+1,1): # range(初期値, 最大値, 増分)
text = ": 素数"

for i in range(2,num,1):
if num % i == 0: # iで割り切れるか
text = ": 素数でない" # iで割り切れた場合は素数ではない
break # 内ループを抜ける

print(str(num) + text)

これでひとまず素数を見つけるプログラムは出来ましたね。
しかし、1とその数以外の約数がないことが素数の条件ですが
それらをすべて計算する必要はあるでしょうか？

次章で詳しく解説していきます！

探索条件について考える

素数の探索範囲

1とその数以外の約数がないことを調べるために
1とその数以外のすべてを調べる必要はないのです

たとえば18の約数は
1, 2, 3, 6, 9, 18 とありますが約数を求めるためには
以下のすべてを計算する必要があるでしょうか？

1 × 18 = 18
2 × 9 = 18
3 × 6 = 18
6 × 3 = 18
9 × 2 = 18
18 × 1 = 18

上半分と下半分の約数は全く同じです

このように、割り切れるということは掛ければその数になるので
セットになる数が必ずあるのです

ここまで見ると18の半分まで計算すれば良い気がしますが
実際には掛けて18になる数
つまり18の平方根まで計算すればよいのです

18の平方根はというと√18
√18 ≒ 4.24
4.24以下の整数になるので4まで計算すれば良いことが分かります。

（厳密には平方根はマイナスも含みますが、ここでは正の約数のため考えません）

探索範囲を平方根にする

先ほどの2~N-1まで求めるプログラムを改良して
2~√Nまで求めるプログラムにします。

import math

MAX = 100 # 探索する最大値
primeNum = [] # 素数を入れる
for num in range(2, MAX+1, 1): # range(初期値, 最大値, 増分)
sqrt = math.sqrt(num) # 平方根を求める
sqrtLow = int(sqrt) # 端数切り捨て

for i in range(2,sqrtLow+1,1):
if num % i == 0: # iで割り切れた場合は素数ではない
break # 内ループを抜ける
else:
primeNum.append(num)

print(primeNum)

ちなみにですが、forのあとのelseはループの正常終了時に実行されます。
＝breakした時は実行されない

素数と判っている数を除外して計算量を減らす

素数自体の判定は効率よく行えるようになりました。
更に計算量を減らす方法として、事前に素数と判っている数を除外できれば無駄な計算が減ります。

新米太郎

ん？　どういうこと？？

新米先生

例えば、2が素数だと分かったら
その倍数（4, 6, 8, 10 …）はそもそも素数かどうかを調べる必要はないですよね。

3(6, 9, 12 …)や7(14, 21, 28 …)など他の素数でも同じです。

つまり、対象の数が素数だと分かったら倍数は素数ではないので
素数の倍数をすべて計算から除外すれば良いのです。

この考え方は探索する最大値が大きくなればなるほど効果を発揮します。
最大値が100程度では大した差になりませんが
それが1000、10000となった時に大きな短縮が見込めます。

倍数を除外するプログラム

2~√Nまで求めるプログラムに
素数の倍数を除外するための配列を追加しています。

import math

MAX = 100 # 探索する最大値
primeNum = [] # 素数を入れる
confirmed = [0] * (MAX +1) # 初期値0で探索の必要有無を入れる

for num in range(2, MAX+1, 1): # range(初期値, 最大値, 増分)
if(confirmed[num] == 1):
continue
sqrt = math.sqrt(num) # 平方根を求める
sqrtLow = int(sqrt) # 端数切り捨て

for i in range(2,sqrtLow+1,1):
if num % i == 0:
# iで割り切れた場合は素数ではない
break # 内ループを抜ける
else:
# ループの正常終了時は素数
primeNum.append(num)
for j in range(num * 2, MAX+1, num): # 素数の倍数を探索済みにする
confirmed[j] = 1

print(primeNum)

また配列の最大値をMAX+1としている理由ですが
1つ多く取ることで添字と判定する数字を同じにして、人間が分かりやすくするためです。