[알고리즘] 정수론 : 오일러의 피

📌 오일러 피 함수 P[N]란?

오일러 피 함수 'φ(N)'은 1부터 N까지의 자연수 중에서 N과 서로소인 자연수의 개수를 구하는 함수
서로소란 두 수의 최대공약수(GCD)가 1인 경우를 의미
예를 들어, φ(6) = 2 ➡️ 1과 5가 6과 서로소이기 때문😊

 

 

📌  오일러 피 함수의 핵심 이론✨

오일러 피 함수는 에라토스테네스의 체와 유사한 방식이라고 생각할 수 있다.

1️⃣ 구하고자 하는 범위만큼 배열 초기화

• P[i]=i로 초기화하여 각 숫자 i에 대해 일단 후보 값을 그대로 설정

2️⃣ 소수인 경우만 처리

• 2부터 시작하여 P[i]=i인 경우, 해당 숫자는 소수
• 이때, 현재 선택된 숫자 K의 배수에 해당하는 값들을 업데이트
• 업데이트 방식:
  P[i]=P[i]−P[i]/K (소수 K에 대해 모든 배수 i에 적용)

3️⃣ 모든 숫자에 대해 반복

• K를 2부터 시작해 배열의 끝까지 반복하며 소수의 배수마다 값을 갱신합니다.

 

🤓 Example:  오일러 피 함수 적용하기

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

2️⃣ 2의 모든 배수마다 P[i] = P[i]/2 연산을 수행해 값을 갱신

ex) 8 ➡️ 8 - 8/2 = 4

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

4️⃣ 배열이 끝날 때까지 반복

 

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

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

이때 후보에서 삭제하는 기준을 6이 아닌 업데이트된 3으로 진행하는 이유는 3의 배수 중 2의 배수인 수들은 즉 3과 2의 공배수는 2의 배수에서 이미 삭제됐기 때문에 중복 삭제를 막기 위함!
이 예시에서는 6을 중복삭제하지 않기 위한 것이다.
최종적으로 답은 2가 된다.
이때 2의 의미는 6이 6이하의 숫자들 중 서로소가 되는 개수가 2개(1, 5)라는 의미가 된다

 

 

✅ 다음 게시글에서 예제 문제로 더 자세히 이해해보도록 하겠습니다!