#Pythonで学ぶアルゴリズム< 素数 >
はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第4弾として素数を扱う．単なる素数判定だけではなく，エラトステネスの篩というアルゴリズムの実装も行う．
素数判定
無数にあるが，素数判定する際には，その数の平方根までを探せば十分であることが知られている．
以下では3つの方法で素数を求めるプログラムを示すが，それらを評価するためのコードも示し，考察する．
素数判定
まずは，原理に基づいある数までの素数を出力するプログラムを実装する．
コードは次に示す．
コード
"""
2020/12/16
@Yuya Shimizu
素数を求める
"""
import math
#素数判定関数
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1): #平方根の範囲まで繰り返し探索する
if n % i == 0:
return False
return True
prime = []
for i in range(100):
if is_prime(i):
prime.append(i)
print(prime)
出力
[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]
100を関数の引数として与え，100までの素数を得ることができた．
評価については最後にほかの2つの方法と比較して行う．
素数判定：エラトステネスの篩
効率よく素数を求める方法として知られている．
具体的には，2で割り切れる数(2の倍数)，2で割り切れる数(3の倍数)，．．．というように，順に除外して，最後には素数だけが残るという考え．
以下に実装したコードを示す．
コード
"""
2020/12/16
@Yuya Shimizu
素数を求める
エラトステネスの篩
"""
import math
def get_prime(n):
if n <= 1:
return []
prime = [2]
limit = int(math.sqrt(n))
#奇数リストの生成
data = [i + 1 for i in range(2, n, 2)]
while limit > data[0]:
prime.append(data[0])
data = [j for j in data if j % data[0] != 0]
return prime + data
print(get_prime(100))
出力
[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]
先ほどと同様の結果が得られた．
3つ目の方法はすでに用意された関数を使う．
素数を求める：sympyを使って
sympyには素数判定する関数isprime()と，求める関数sieve.primerange()というのがある．
これはすでに用意された関数であるから，実装は非常に簡単である．実装した後，ほかの2つの方法と比較して評価を行う．
コード
"""
2020/12/16
@Yuya Shimizu
素数を求める
"""
from sympy import sieve
print([i for i in sieve.primerange(1,100)])
出力
[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]
たったこれだけのプログラムで，ほかの方法と同じ結果が得られた．
では最後に，これら3つのプログラムの評価を実行時間を基に行う．
評価テスト
それぞれの実装プログラムを以下に示す．
コード１
"""
2020/12/16
@Yuya Shimizu
素数を求める
"""
import math
import time
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
# 実行時間の評価
start = time.time()
prime = []
for i in range(100000):
if is_prime(i):
prime.append(i)
print(prime)
process_time = time.time() - start
print(process_time)
コード２
"""
2020/12/16
@Yuya Shimizu
素数を求める
エラトステネスの篩
"""
import math
import time
def get_prime(n):
if n <= 1:
return []
prime = [2]
limit = int(math.sqrt(n))
#奇数リストの生成
data = [i + 1 for i in range(2, n, 2)]
while limit > data[0]:
prime.append(data[0])
data = [j for j in data if j % data[0] != 0]
return prime + data
start1 = time.time()
print(get_prime(100000))
process_time1 = time.time() - start1
print(process_time1)
コード３
"""
2020/12/16
@Yuya Shimizu
素数を求める
"""
from sympy import sieve
import time
start = time.time()
print([i for i in sieve.primerange(1,100000)])
process_time = time.time() - start
print(process_time)
結果
今回は100までの素数と1000000までの素数を求めることをそれぞれのプログラムで行い，時間を測定した．以下にその結果をまとめる．
| 素数 | プログラム１(原理) | プログラム２(エラトステネスの篩) | プログラム３(sympyの関数) |
|---|---|---|---|
| 100まで [s] | 0.00 | 0.01 | 0.02 |
| 1000000まで [s] | 8.78 | 5.87 | 4.71 |
100までの素数に関しては，処理が短いため違いはそこまでないが，素数を探す範囲を広げるほど，処理時間に差が出た．特にプログラム１に関してはほかの2つの方法よりも遅い．言い換えるとほかの2つの方法が効率よく素数を探すことができていいるといえる．さらにプログラム３に関しては効率よく素数を求めるためのエラトステネスの篩に基づいたプログラムよりも1秒も早い．プログラム３はsympyの関数を使っており，プログラムも簡単なうえに処理時間もかなり短縮できているという結果が得られた．
感想
プログラム３が一番早いことには驚いた．予想ではエラトステネスの篩のプログラムが一番早いかと思っていたが，sympyの関数が優秀だった．プログラムも簡単なため，素数を求める際にはsympyの関数を使えばよいのではと思った．しかし，sympyの中身を知らないため，安易には言えないのかもしれない．
また，原理に基づいたプログラム１との比較で，改めてアルゴリズムの有用性を感じられた．このような感覚はアルゴリズムを学習しようという士気をよりいっそう高めてくれる．
参考文献
Pythonで始めるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
増井 敏克 著 翔泳社