素数列挙 (エラトステネスの篩)
(NumberTheory/Prime/eratosthenes_sieve.py)

• View this file on GitHub
• Last update: 2021-03-05 15:07:14+09:00

概要

$O(n\log \log n)$ で素数列挙を行うアルゴリズム。

使い方

eratosthenes_sieve(n: int) -> Tuple[List[int], List[int]]
n 以下の素数のリストと、素数かどうかの判定テーブルを返す。計算量 $O(n \log \log n)$

Verified with

• TestCase/AOJ/ALDS1_1_C.eratosthenes_sieve.test.py

Code

def eratosthenes_sieve(n):
    is_prime_tbl = [True] * (n + 1)
    is_prime_tbl[0] = False
    is_prime_tbl[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime_tbl[i]:
            continue
        for j in range(2 * i, n + 1, i):
            is_prime_tbl[j] = False
    prime_list = [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