• 오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수
  • 서로소: 공약수가 1 이외에 없는 것

핵심 이론

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

오일러 피 함수의 원리

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

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

• https://www.acmicpc.net/problem/11689
• GCD(n, k) = 1(1 ≤ k ≤ n) → 1~n 사이에서 두 수의 최대공약수가 1인 것 → 1~n 사이에서 서로소 → 오일러 피 함수
• result: 서로소의 개수
• n: 현재 소인수 구성