정수론 : 오일러 피

오일러 피

오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있다고하지만 실제 코딩 테스트에 사용하기 위한 구현 부분만 알아보겠다.

오일러 피의 핵심 이론
오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.

오일러 피 함수의 원리

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

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

이 원리가 정확하게 이해되지 않을 수 있다. 수학적인 측면에서 좀 더 알아보자.
•초기 상태: (6) = 6-> 서로소가 될 수 있는 후보의 개수로 초기화(1, 2, 3, 4, 5, 6)
• 2의 배수로 인한 탈락-> (6)= 6-(6/2)= 3(1, 3, 5)
• 3의 배수로 인한 탈락-> (6)= 3-(3/3)= 2(1, 5)

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

관련 문제

 

https://www.acmicpc.net/problem/11689

11689번: GCD(n, k) = 1

 

책 <Do It! 알고리즘 코딩테스트>_김종관 지음, 이지스퍼블리싱 출판사

학교 알고리즘 수업 강의자료 등 여러 자료 참고해서 공부함.