오일러 피 함수

소수 계산과 함께 많이 쓰이는 오일러 피 함수 입니다.

피 함수는 자신보다 작은 양수 중에서 자기 자신과의 최대 공약수가 1인 숫자가 몇 개인지를 나타냅니다.

따라서 소수 p의 경우 모든 숫자가 서로 소 이기 때문에 다음과 같이 쓸 수 있습니다.

φ(p) = p - 1

그리고 p와 q가 서로 소인 경우 다음과 같은 식이 성립합니다.

φ(pq) = φ(p)φ(q)

자세한 설명은 다음 링크를 참고하세요.

https://en.wikipedia.org/wiki/Euler%27s_totient_function

def totient(n):
    phi = int(n > 0 and n)
    for p in range(2, int(n ** .5) + 1):
        if not n % p:
            phi -= phi // p
            while not n % p:
                n //= p
    if n > 1: phi -= phi // n
    return phi