오일러의 피

오일러의 피

 

P[N] : 1부터 N까지 범위에서 N과 서로소인 자연수의 개수

 

원리

1. 구하고자 하는 오일러 피의 범위만큼 리스트를 자기자신의 인덱스 값으로 초기화한다.

2. 2부터 시작해 현재 리스트의 값과 인덱스가 같으면 (소수) 현재 선택된 숫자(k)의 배수에 해당하는 수의 리스트를 끝까지 탐색하여 P[i] = P[i] - P[i] / k 연산을 수행한다. (i는 k의 배수)

3. 리스트의 끝까지 2를 반복하여 오일러의 피 함수를 완성한다.