sympy の primerange と sieve.primerange の違い

はじめに

sympy.ntheory.generate.primerange と sympy.ntheory.generate.sieve.primerange はどちらも指定する範囲内の素数を列挙してくれる。

>>> from sympy.ntheory.generate import sieve, primerange
>>> list(primerange(3, 20))
[3, 5, 7, 11, 13, 17, 19]
>>> list(sieve.primerange(3, 20))
[3, 5, 7, 11, 13, 17, 19]

ただし、

• sieveはメモリを確保する
• sieveは最大値が決まっている
• primerangeはsieveを利用する

という違いがある。

sieveはメモリを確保する

sieve(篩)という名前から予測できると思うが、sieveの裏にはエラトステネスの篩が実装されている。なので、例えば、

sieve.primerange(1000, 2000)

というコードを実行すると、裏では2000以下の素数リストが作成される。1000以下の素数については不要であるのにもかかわらずだ。対してprimerangeは、sieveに保存されていればそれを使うが、基本的には指定された範囲の数に対して素数判定を行っている。なので、実行後にメモリ上には残らない。

sieveは最大値が決まっている

sieveは、既知の素数をリストとして保存しているが、要領削減のため一般的なlist形式ではなく、arrayを使っている。コンパクトに表現できる代わりに、C言語の型のサイズの影響を受けるので、sympy 1.12以前では$2^{31}-1$より大きい素数、1.13以降では$2^{32}-1$より大きい素数は扱えない。

つまり、

sieve.primerange(2**100, 2**100+1000)

のような処理はエラーになる。対してprimerangeは、先ほども述べた通りの実装なので

primerange(2**100, 2**100+1000)

が問題なく実行できる。

primerangeはsieveを利用する

sieve.extend(100)

を実行すると、100以下の素数リストが確保され、この範囲ではsieve.primerangeもprimerangeも同様にリストを使って答えを返す。

100以上の場合、sieveは、素数リストを伸長することは既に述べた。では、primerangeの場合はどうだろうか？　sympy 1.12以前では、逐一素数判定を行うため効率が悪かった。しかし、エラトステネスの篩のアルゴリズムを応用すれば、$100^2$までは篩による効率的な列挙方法が存在する。そこで、sympy 1.13以降では、既知の素数の最大値の2乗以下であれば、(結果は保存しないが)篩アルゴリズムを実行するようになっている。

まとめ

primerange と sieve.primerange はどちらも指定する範囲内の素数を列挙する関数だが、どちらを使うべきかは使用場面によって異なるので、アルゴリズムの特性を良く理解していないと効率的な素数列挙ができない。