コンテンツにスキップ

0650: 無限素数ストリーム

問題

素数を小さい順に無限に生成するジェネレータ関数 primes() を実装してください。

def primes() -> Iterator[int]: ...

古典的なエラトステネスの篩は、上限 \(N\) を先に決めて長さ \(N\) の表を篩います。 本問では上限を決めず、増分篩で実装します。 すなわち、合成数をキー、その合成数を割り切ると判明している素数のリストを値とする辞書だけを主要な内部状態として持ち、候補の整数を 2 から昇順に調べる過程でこの辞書を少しずつ更新していきます。

制約

  • primes() は引数を取りません。生成される列は無限で、打ち切りは呼び出し側（itertools.islice など）が行います。
  • 生成済みの素数を列として保持し、新しい候補をそれらで順に割る試し割りは禁止します。
  • 上限や生成する素数の個数をあらかじめ仮定する定数を持ってはいけません。

例

>>> from itertools import islice
>>> list(islice(primes(), 10))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
>>> next(islice(primes(), 999, None))  # 1000番目の素数
7919

発展

  • 生成済みの素数のリストで候補 \(n\) を \(\sqrt{n}\) 以下の素数で試し割りする素朴な実装も書き、\(N\) 番目の素数を得るまでの総計算量を増分篩と比較してください。
  • 候補 \(n\) を処理している時点での辞書の要素数を測定してください。素数を辞書へ登録する位置を選ぶことで、要素数を \(\pi(\sqrt{n})\) 程度（\(\sqrt{n}\) 以下の素数の個数）に抑えられます。

参考