オイラーの $\varphi$ 関数
(NumberTheory/misc/euler_phi.py)

• View this file on GitHub
• Last update: 2021-08-12 23:00:53+09:00

使い方

euler_phi(n: int) -> int
正の整数 $n$ について、$n$ と互いに素な $n$ 以下の正の整数の個数を返す。計算量 $O(\sqrt{n})$

euler_phi_table(n: int) -> List[int]
$n$ 以下の $\varphi (n)$ をすべて求めたテーブルを返す。計算量 $O(n \log \log n)$

Verified with

• TestCase/AOJ/NTL_1_D.test.py
• TestCase/unittest/euler_phi_table.unittest.test.py

Code

def euler_phi(n):
    ans = n
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            while n % i == 0:
                n //= i
            ans -= ans // i
    if n > 1:
        ans -= ans // n
    return ans


def euler_phi_table(n):
    phi = [i for i in range(n + 1)]
    for i in range(2, n + 1):
        if phi[i] == i:
            for j in range(i, n + 1, i):
                phi[j] -= phi[j] // i
    return phi

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