오일러 피

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

 

오일러 피의 핵심 이론

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

서로소란?
두 수 사이의 관계에서 공통되는 약수가 최대 1이며 1밖에 없는 수를 뜻한다.