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]]

for 文の方が while 文よりも速い気配があるので、for 文で書きました。その検証は下のサイトでやりました。for 文の方が綺麗に書けますしね。素因数分解するときは while 文の方が早かったです。なぜかは、わかりません。

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 で代用した。

素数の判定を重複して行いません。１度だけしか行いません。
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 を用いて
一時的に素数ではない数をリストとして保存している。

（番外編）ワンライナーで素数リストを得る

これはエラトステネスの篩では、ありません。速度的には 1 より少し遅いくらいでした。自分のパソコンだと i=3 を代入すると計算が終わらない。しかし、こんなやり方、思いつくなんて凄すぎる...。Twitter の "だよ〜" ってコメントなんだよ、軽すぎるよ (´；ω；`)ﾌﾞﾜｯ

# 素数リスト 2**i 桁以下
primes = lambda i: primes(i - 1) + [k for k in range(10**2**(i-1), 10**2**i) if all(k % p for p in primes(i - 1))] if i else [2, 3, 5, 7]

# 素数リスト 2**i 桁以下
def primes(i):
    if i:
        # 素数リスト 2**(i-1) 桁以下
        L = primes(i - 1)

        # 素数リスト 2**(i-1)+1 桁以上 2**i 桁以下
        n = range(10**2**(i-1), 10**2**i)
        M = [k for k in n if all(k % p for p in L)]

        # 素数リスト 2**i 桁以下
        return L + M
    else:
        # 素数リスト 2**0 桁以下
        return [2, 3, 5, 7]

pythonで素数表と素数判定するコードだよ～ - にんㄘ゛ん

◯ ポイント

def primes(i):
        ...
        # 素数リスト 2**(i-1)+1 桁以上 2**i 桁以下
        n = range(10**2**(i-1), 10**2**i)
        M = [k for k in n if all(k % p for p in L)]
        ...

2**(i-1)+1 桁以上 2**i 桁以下の合成数（素数でない数）は、 2**(i-1) 桁以下の素数を素因数に持ちます。逆に言えば、2**(i-1)+1 桁以上 2**i 桁以下の合成数（素数でない数）は、2**(i-1)+1 桁以上の素数を素因数に持ちません。

2 桁の合成数は、1 桁以下の素因数を持ちます。3 桁以上4 桁以下の合成数は、2桁以下の素因数を持ちます。5 桁以上 8 桁以下の合成数は、4 桁以下の素因数を持ちます。

例えば 2 桁の合成数で 1 桁の素因数を持たない数を考えて見てください。存在しません。逆に言えば、例えば 2 桁の素数を使って 2 桁の合成数を作って見てください。作ることはできません。

これは、任意の 2 桁の素数 p, q について考えると、必ず p * q >= 100 となるからです。