소인수 개수

양의 정수 \( n \)에 대해 \( n \)보다 작은 양의 정수 중에서 \( n \)과 서로소인 수의 개수를 구할 때 오일러의 피 함수 \(\phi(n)\)를 사용한다.

 

 

(Euler's Totient Function)

 

1. \( n \)의 소인수를 찾는다.
2. \( n \)의 소인수를 이용하여 피 함수 값을 계산한다.

 

 

\[
\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \ldots \left(1 - \frac{1}{p_k}\right)
\]
여기서 \( p_1, p_2, \ldots, p_k \)는 \( n \)의 소인수들이다.

 

def compute_totient(n):
    if n == 0:
        return 0
    # n이 0일 경우 0을 반환. 이는 0에 대한 특별 처리를 의미한다.

    result = n
    # result를 n으로 초기화. 최종적으로 \phi(n)의 값을 저장할 변수다.

    p = 2  # 초기 소수

    while p  p <= n:  # p의 제곱이 n보다 작거나 같은 동안 반복
        if n % p == 0:  # n이 p로 나누어 떨어지면 p는 n의 소인수이다.
            while n % p == 0:
                n //= p  # n이 더 이상 p로 나누어지지 않을 때까지 n을 p로 나눈다. 이는 n에서 p의 모든 배수를 제거하는 과정이다.
            result -= result // p  # p가 소인수인 경우 \phi(n)의 값을 갱신한다.

        p += 1  # 다음 소수로 이동

    if n > 1:
        result -= result // n  # 반복문이 끝난 후 n이 1보다 크면 마지막 남은 n은 소수다.
    return result  # 최종 계산된 \phi(n)의 값을 반환


def main():
    import sys
    input = sys.stdin.read  # 표준 입력으로부터 모든 데이터를 읽어오는 함수를 정의
    data = input().strip().split()  # 입력된 데이터를 공백을 기준으로 분리하여 리스트에 저장
    for number in data:
        n = int(number)  # 현재 숫자를 정수형으로 변환
        if n == 0:
            break  # 입력이 0이면 반복을 종료
        print(compute_totient(n))  # 오일러의 피 함수 값을 계산하여 출력

if __name__ == "__main__":

 

 

 

각 숫자에 대해 오일러의 피 함수 계산:
   - data 리스트의 각 요소를 정수형으로 변환하여 n에 저장한다.
   - n이 0이면 반복을 종료한다.
   - compute_totient(n) 함수를 호출하여 \(\phi(n)\) 값을 계산하고 출력한다.

 오일러의 피 함수 계산 (compute_totient 함수):
   - 주어진 n에 대해 오일러의 피 함수 값을 계산한다.
   - 초기 소수 p를 2로 설정하고, \(\sqrt{n}\) 이하의 소수들에 대해 반복하면서 소인수를 찾고 \(\phi(n)\) 값을 갱신한다.
   - 모든 소인수에 대해 처리가 끝난 후, 최종적으로 남은 값이 1보다 크면 그 값도 소수이므로 \(\phi(n)\) 값을 갱신한다.