Posted at

最初のN個の素数を生成する in Python3

最初の $N$ 個の素数を生成する方法を何通りか挙げて、計算時間を測定してみました。


素数の生成

素数が入ったlistを返す関数を作ります。


1. 愚直な方法

整数 $x$ を $2,3,4,5,\dots$ で割って素数を判定します。

from math import sqrt

def is_prime_simple(x):
for i in range(2, int(sqrt(x)) + 1):
if x % i == 0:
return False
return True

def simple(n):
primes = []
x = 2
while len(primes) < n:
if is_prime_simple(x):
primes.append(x)
x += 1

return primes


2. ちょっと工夫した方法

整数 $x$ を $x$ より小さい素数で割って素数を判定します。

from math import sqrt

def is_prime_using_list(x, primes):
for p in primes:
if p > sqrt(x):
return True

if x % p == 0:
return False

return True

def using_prime_list(n):
primes = []
x = 2
while len(primes) < n:
if is_prime_using_list(x, primes):
primes.append(x)
x += 1

return primes


3. エラトステネスのふるい

おなじみの速いやつ。エラトステネスのふるいはある整数以下の素数を生成する手法なので、整数の上限を決めてやる必要があります。$n\geq 6$ のとき、$n$ 番目の素数 $p_n$ について、

p_n < n (\ln(n) + \ln(\ln n))

という性質がある1ので、これを使って上限を決めます。

from math import log

def eratosthenes(n):
max_num = int(n * (log(n) + log(log(n)))) + 1
work = [0] * max_num

primes = []
for i in range(2, max_num):
if len(primes) >= n:
break

if work[i] == 0:
primes.append(i)

for j in range(i, max_num, i):
work[j] = 1

return primes


実行時間測定

次のコードを使用して、実行時間を測定します。

def measure_time(func, n):

import time

start = time.time()
result = func(n)
elapsed_time = time.time() - start

print("=== {} === ".format(func.__name__))
print("elapsed_time: {}[sec]".format(elapsed_time))
print("result size: {}".format(len(result)))
print("last value: {}".format(result[-1]))

if __name__ == '__main__':
n = 100000
measure_time(simple, n)
measure_time(using_prime_list, n)
measure_time(eratosthenes, n)


実行結果


  • PC: MacBook Pro (Retina, 13-inch, Early 2015)

  • OS: macOS High Sierra (バージョン 10.13.6)

  • Python: バージョン 3.6.5

で実行しました。結果は以下の通りです。

=== simple ===

elapsed_time: 7.736111879348755[sec]
result size: 100000
last value: 1299709
=== using_prime_list ===
elapsed_time: 4.412992000579834[sec]
result size: 100000
last value: 1299709
=== eratosthenes ===
elapsed_time: 2.4267871379852295[sec]
result size: 100000
last value: 1299709





  1. Wipikediaの『素数定理』より