[Coding Test] inflearn(9)

1. 오일러 피

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

오일러 피 함수의 핵심 이론

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

오일러 피 함수의 원리

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

2. 2의 모든 배수마다 P[i] = P[i] - P[i]/2 연산을 수행해 값을 갱신한다. 예를 들어 8 = 8-(8/2)를 통해 4를 계산한다.
   

3. 소수 구하기에서 배수를 지우는 부분만 P[i] = P[i] - P[i]/K로 변경하면 오일러 피 함수를 간단히 구현할 수 있다.
   

4. 배열이 끝날 때까지 반복한다.
   

2. 오일러 피의 실전 문제