알고리즘 개념[기초] - 오일러 피

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

여기서 '서로소' 란,
1 이외에 공약수가 없는 두 수 이상의 자연수 관계를 뜻합니다.

문제 출제 빈도 자체는 높지는 않지만, 원리를 알지 못하면 문제 접근이 어렵습니다.

오일러 피의 핵심 이론

• 원리는 에라토스테네스 체와 비슷합니다.

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