素数列挙 (区間篩)
(NumberTheory/Prime/segment_sieve.py)

• View this file on GitHub
• Last update: 2021-03-05 16:39:32+09:00

概要

区間範囲に対して素数列挙を行うアルゴリズム。区間 $[l, r)$ についての制約が

• $1 \le l \lt r \le 10^9$
• $r − l \le 10^6$

のようなときに使用可能。

使い方

segment_sieve(l: int, r: int) -> Tuple[List[int], List[int]]
l 以上 r 未満の整数について、素数のリストと素数かどうかの判定テーブルを返す。計算量 $O(\sqrt r + (r - l)\log\log r)$

Verified with

• TestCase/unittest/segment_sieve.unittest.test.py

Code

def segment_sieve(l, r):
    sqrt_r = int(r ** 0.5)
    is_prime_sqrt = [True] * (sqrt_r + 1)
    is_prime_sqrt[0] = False
    is_prime_sqrt[1] = False
    is_prime_tbl = [True] * (r - l)
    if l == 0:
        is_prime_tbl[0] = False
        is_prime_tbl[1] = False
    if l == 1:
        is_prime_tbl[0] = False

    for i in range(2, sqrt_r + 1):
        if not is_prime_sqrt[i]:
            continue
        for j in range(2 * i, sqrt_r + 1, i):
            is_prime_sqrt[j] = False
        for j in range(max((l + i - 1) // i, 2) * i, r, i):
            is_prime_tbl[j - l] = False

    prime_list = [l + i for i, flag in enumerate(is_prime_tbl) if flag]
    return prime_list, is_prime_tbl

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page