素数列挙 + 素因数分解 (線形篩)
(NumberTheory/Prime/linear_sieve.py)

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

概要

$O(n)$ で素数列挙を行うアルゴリズム。副産物の最小素因数によって $O(\log n)$ で素因数分解ができる。

使い方

linear_sieve(n: int) -> Tuple[List[int], List[int]]
整数 n 以下の素数のリストと、各整数について最小素因数のテーブルを返す。計算量 $O(n)$

prime_factors(n: int, mindiv_factor: Sequence[int]) -> List[int]
整数 n を素因数分解した結果のリストを返す。線形篩によって求めた最小素因数のテーブル mindiv_factor を引数に取る。計算量 $O(\log n)$

Verified with

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

Code

def linear_sieve(n):
    prime_list = []
    mindiv_factor = [i for i in range(n + 1)]
    for i in range(2, n + 1):
        if mindiv_factor[i] == i:
            prime_list.append(i)
        for p in prime_list:
            if p * i > n or p > mindiv_factor[i]:
                break
            mindiv_factor[p * i] = p
    return prime_list, mindiv_factor


def prime_factors(n, mindiv_factor):
    pf = []
    while mindiv_factor[n] != 1:
        pf.append(mindiv_factor[n])
        n //= mindiv_factor[n]
    return pf

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