Qiitaからの移植です。
最初の 個の素数を生成する方法を何通りか挙げて、計算時間を測定してみました。
素数の生成
素数が入ったlistを返す関数を作ります。
1. 愚直な方法
整数 を
で割って素数を判定します。
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. ちょっと工夫した方法
整数 を
より小さい素数で割って素数を判定します。
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. エラトステネスのふるい
おなじみの速いやつ。エラトステネスのふるいはある整数以下の素数を生成する手法なので、整数の上限を決めてやる必要があります。 のとき、
番目の素数
について、
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