オイラーのφ関数（Python）
(num_theory/Eulers_totient_function.py)

• View this file on GitHub
• Last update: 2023-09-17 18:47:10+09:00

概要

オイラーのφ関数を返します。

計算量

• NULL

補足

sympyを使っていいなら下記コードのほうが断然早い

from sympy import totient

n = int(input())
result = totient(n)
print(result)

Verified with

• verify-check/AOJ-NTL-1-D.test.py

Code

def Eulers_totient_function(N):
    # 初期値
    result = N
    
    # 素因数分解用の数字
    num = 2
    
    # numがN**(1/2)になるまで繰り返し
    while num**2 <= N:
        # numがresultの因数の場合はφ関数に操作を行う
        if N%num==0:
            result = (result//num)*(num-1)
            
            # numを因数に含んでいる限り操作を行い、Nに含まれる因数numをなくしている
            while N%num==0:
                N//=num
                
        # numを変更して次の素因数を探す
        num += 1
        
    # まだ素因数が残っている場合、φ関数を操作する
    if N>1:
        result = (result//N)*(N-1)
    
    return result

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.1/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.1/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page