오일러 피 함수(Euler’s Totient Function)는 어떤 수 n이 주어졌을 때, 1부터 n까지의 자연수 중에서 n과 서로소인 수의 개수를 구하는 함수입니다.

1. 오일러 피 함수의 원리

오일러 피 함수는 다음의 3단계를 통해 값을 계산할 수 있습니다.

1단계: 초기화

• 구하고자 하는 오일러 피의 범위만큼 배열을 생성하고, 각 요소를 자기 자신의 인덱스 값으로 초기화합니다.

2단계: 소수의 배수 처리

• 2부터 시작하여 현재 배열 값과 인덱스가 같다면(즉, 해당 값이 소수라면),
  • 해당 소수의 모든 배수 P[i]에 대해 P[i] = P[i] - P[i] / k 연산을 수행합니다.
  • 여기서 k는 현재 소수이며, i는 k의 배수입니다.

3단계: 전체 탐색

• 배열의 끝까지 2단계를 반복하여 최종적으로 오일러 피 함수를 구합니다.

2. 예제 문제: 백준 11689번 “GCD(n, k) = 1”

문제 설명: 주어진 n에 대해 1부터 n까지의 자연수 중 n과 서로소인 수의 개수를 구하는 프로그램을 작성하시오.

2.1 코드 구현 (Python)

# 오일러 피 함수 구현

def GCD(n):
    result = n  # 초기값: n
    p = 2  # 2부터 시작
    while p * p <= n:  # n의 소인수 찾기
        if n % p == 0:  # p가 소인수라면
            while n % p == 0:
                n //= p  # p로 나눠줌
            result -= result // p  # 공식 적용
        p += 1
    if n > 1:  # 마지막 남은 소수가 있다면
        result -= result // n
    return result

# 입력 및 실행
n = int(input())
print(GCD(n))

2.2 코드 분석과 오일러 피 함수 적용

위 코드에서 오일러 피 함수의 3단계가 어떻게 적용되는지 살펴보겠습니다.

1단계: 초기화

result = n  # 초기값을 n으로 설정
p = 2  # 2부터 시작하여 소인수를 찾음

• result 값을 n으로 초기화합니다.
• p를 2로 설정하여 가장 작은 소수부터 시작합니다.

2단계: 소수의 배수 처리

while p * p <= n:
    if n % p == 0:
        while n % p == 0:
            n //= p  # p로 나눠줌
        result -= result // p  # 공식 적용
    p += 1

• p가 n의 소인수인지 확인하고, n을 해당 소인수로 나누어 제거합니다.
• 제거된 후, result -= result // p 연산을 수행하여 오일러 피 값을 갱신합니다.

3단계: 전체 탐색

if n > 1:
    result -= result // n

• 마지막으로 남은 n이 소수라면, result -= result // n을 실행하여 최종 값을 구합니다.

3. 예제 실행 결과

입력 예시

10

출력 예시

4

1부터 10까지의 자연수 중 10과 서로소인 숫자는 {1, 3, 7, 9}이므로 φ(10) = 4입니다.

4. 정리