素数の生成

素数が入った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))

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

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

Wipikediaの『素数定理』より↩

Beyond the State-of-the-Art

最先端を超えたいと思ってる(大嘘)エンジニアのブログ

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