素因数分解 (試し割り法)
(NumberTheory/Prime/prime_factors.py)

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

概要

$O(\sqrt n)$ で素因数分解を行うアルゴリズム。

使い方

prime_factors(n: int) -> List[int]
整数 n を素因数分解した結果のリストを返す。計算量 $O(\sqrt n)$

prime_factors_distinct(n, int) -> List[int]
整数 n を素因数分解し、素因数の重複を除いた結果のリストを返す。計算量 $O(\sqrt n)$

prime_factors_compress(n, int) -> List[Tuple[int, int]]
整数 n を素因数分解し、(素因数, 素因数の個数) の組として結果のリストを返す。計算量 $O(\sqrt n)$

Verified with

• TestCase/AOJ/NTL_1_A.test.py

Code

def prime_factors(n):
    factors = []
    for k in range(2, int(n ** 0.5) + 1):
        while n % k == 0:
            factors.append(k)
            n = n // k
    if n != 1:
        factors.append(n)
    return factors


def prime_factors_distinct(n):
    factors = []
    for k in range(2, int(n ** 0.5) + 1):
        if n % k == 0:
            factors.append(k)
            while n % k == 0:
                n = n // k
    if n != 1:
        factors.append(n)
    return factors


def prime_factors_compress(n):
    factors = []
    for k in range(2, int(n ** 0.5) + 1):
        cnt = 0
        while n % k == 0:
            cnt += 1
            n = n // k
        if cnt != 0:
            factors.append((k, cnt))
    if n != 1:
        factors.append((n, 1))
    return factors

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