Python で素数のリストを得る方法 エラトステネスの篩


3 つの書き方を比較検討しました。

項番 項目 時間
1 簡単なもの 0.9157630139998219
2 高速化 0.16211261399985233
3 集合 0.5873824189993684

計測に使用したコード sieve_of_eratosthenes.py


1. 簡単なもの

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


参考にしたサイトは、下記のサイトから抜粋しました。
「ディビジョン・サム」問題解説|CodeIQ MAGAZINE


2. 高速版

5 倍くらい早くなる。

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]



3. 集合(OrderedDict で代用)

しかしそこまで速くならず、簡単なものより 1.5 倍速いくらい。
アルゴリズム的には一番速いはずだけど。

import collections


def primes_ordered_dict(n):
    #
    prime_list = []
    non_prime_list = []
    number_dict = collections.OrderedDict(
        ((i, None) for i in range(n + 1)))
    #
    del number_dict[0]
    del number_dict[1]
    while True:
        # get prime
        prime, _ = number_dict.popitem(False)
        prime_list.append(prime)
        # break
        if prime * prime > n:
            break
        # get non primes
        non_prime_list.append(prime * prime)
        for k in number_dict:
            if prime * k <= n:
                non_prime_list.append(prime * k)
            else:
                break
        # delete non primes
        for non_prime in non_prime_list:
            del number_dict[non_prime]
        non_prime_list.clear()

    # add rest of numbers as prime
    prime_list.extend(
        [prime for prime, _ in number_dict.items()])

    return prime_list


2. 高速版のアルゴリズムでも
既に素数でないと判定されたものにも複数回、
素数でないと判定しています。
is_prime[j] = False を実行しています。

例えば 3 * 4, 3 * 6, 3 * 8 のような数です。
素数 * 既に素数と判定された数の倍数

そこで集合を用いて、同じ処理を繰り返し行わないようにしたいと考えた。
Python の set は Ordered ではないので OrderedDict で代用した。

素数の判定を重複して行いません。1度だけしか行いません。
del number_dict[non_prime] を実行しています。

しかしそこまで速くならず、簡単なものより 2 倍速いくらい。
アルゴリズム的には一番速いはずだけど。

Python は、四則演算やらなんやらが遅いので
何が原因かはいまいちよくわからない。
Python を高速化したい

やったことないですが OrderedDict に該当するモジュールを
C 言語で書き直して比較したら、また違うのかなと思ったりもします。
1. C や C++ による Python の拡張
100万倍速いプログラムを書く | Qiita

その時は for 文の中でも del number_dict[non_prime]
できるようにしようかな。
そしたら Python 側のコードはもっと綺麗になる。

できいないので上のコードでは non_prime_list を用いて
一時的に素数ではない数をリストとして保存している。