알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 오일러 피

07-2 오일러 피

오일러 피 함수 P(N) = 1부터 N까지 범위에서 N과 서로소인 자연수의 개수

ex) P[6] = 1~6 범위에서 6과 서로소(공약수가 1이외에 없는 것)인 자연수 개수 

P[6] = 2 (1, 5 => 2개)

 

오일러 피의 핵심 이론

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

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

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

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

 

ex)