오일러 피 함수는 P[N]의 정의는 1부터 N까지의 범위에서 N과 서로소인 자연수의 개수를 뜻한다.

<aside> 💡 서로소 : 공약수가 1이외에 없는 것을 말함. ex) P[6] = 1~6 범위에서 6과 서로소인 자연수 개수 (1과 5) ∴ P[6] = 2

</aside>

오일러 피의 핵심 이론

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

오일러 피 함수의 원리

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

오일러 피 함수의 원리 이해하기

[11689] 오일러 피 함수 구현하기