오일러 피 (Euler’s Totient) - 서로소 개수 구하기

 

수학 기반 알고리즘 문제 중에서는 정수론(Number Theory) 개념을 묻는 문제가 종종 등장한다.

그중 대표적인 개념이 바로 오일러 피 함수(Euler’s Totient Function) 이다.

처음 보면 다소 생소할 수 있지만, 원리를 이해하면 에라토스테네스의 체와 매우 유사한 구조를 가진다.
https://xeungcoding.tistory.com/58

소수(prime number) 구하기 - 에라토스테네스의 체

 

이번 글에서는 오일러 피 함수의 정의와 원리,
그리고 배열을 이용한 계산 방법을 중심으로 정리해보려고 한다. ✍️

 

 

---

 

 

오일러 피 함수란?

오일러 피 함수 P[N] 의 정의는 다음과 같다.

1부터 N까지의 자연수 중에서 N과 서로소인 수의 개수

 

여기서 “서로소”란 두 수의 최대공약수(GCD)가 1인 경우를 말한다.

 

예를 들어, N이 10인 경우

• 1부터 10까지 중에서 10과 서로소인 수는 1, 3, 7, 9
• 따라서, P[10] = 4

이처럼 오일러 피 함수는 “특정 수와 서로소인 수의 개수”를 계산하는 함수이다.

 

 

---

 

 

오일러 피 함수의 핵심 아이디어 

오일러 피 함수의 계산 원리는 에라토스테네스의 체와 매우 유사하다.

 

차이점은

• 소수를 “지우는 것”이 아니라
• 각 수의 값을 갱신(update) 하는 방식이라는 점이다.

핵심 아이디어는 다음과 같다.

"어떤 수 N이 소수 K를 약수로 가진다면, N과 서로소가 아닌 수의 비율은 1/K 만큼 존재한다."

이를 이용하여 배열 값을 점진적으로 줄여 나가는 방식으로 계산한다.

 

 

---

 

 

오일러 피 함수 계산 과정 🔁

1. 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스값으로 초기화한다.
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] - P[i] / K 연산을 수행한다(i는 K의 배수).
3. 배열의 끝까지 2번을 반복하여 오일러 피 함수를 완성한다.

 

다음 예를 통해 오일러 피 함수를 좀 더 자세히 알아본다.

 

1. 구하고자 하는 범위까지 배열을 생성한 후 2를 선택한다.

 

2. 2의 모든 배수마다 P[i] = P[i] - P[i] / 2 연산을 수행해 값을 갱신한다. 예를 들어 8 = 8 - (8 / 2)를 통해 4를 계산한다.

 

3. 소수 구하기에서 배수를 지우는 부분만 P[i] = P[i] - P[i] / K로 변경하면 오일러 피 함수를 간단히 구현할 수 있다. 탐색을 계속 진행하면서 N = φ(N)인 곳(소수)을 찾아 값을 갱신한다.

 

4. 배열이 끝날 때까지 반복한다.

 

 

---

 

 

수학적으로 오일러 피 함수 이해하기 

이 원리가 정확하게 이해되지 않을 수 있어, 수학적인 측면에서 좀 더 알아본다.

• 초기 상태: φ(6) = 6 → 서로소가 될 수 있는 후보의 개수로 초기화(1, 2, 3, 4, 5, 6)
• 2의 배수로 인한 탈락 → →  = 6 - (6 / 2) = 3(1, 3, 5)
• 3의 배수로 인한 탈락 →  φ(6) = 3 - (3 / 3) = 2(1,5)

이때 후보에서 삭제하는 기준을 6이 아닌 업데이트된 3으로 진행하는 이유는 3의 배수 중 2의 배수인 수, 즉 3과 2의 배수에서 이미 삭제됐기 때문에 중복 삭제를 막기 위함이다.

이 예시에서는 6을 중복 삭제하지 않기 위한 것이다. 최종적으로 φ(6) = 2가 된다. 이때 2의 의미는 숫자 6과 6 이하의 숫자 중 서로소가 되는 개수가 2개 (1, 5)라는 뜻이 된다.

 

 

---

 

 

시간 복잡도 ⏰

오일러 피 함수를 배열 기반으로 구현할 경우 시간 복잡도는 다음과 같다.

O(N log log N)

 

에라토스테네스의 체와 유사한 구조이기 때문에 매우 효율적으로 계산할 수 있다.

따라서 큰 범위의 N에 대해서도 빠르게 값을 구할 수 있다.