오일리 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수이다.
오일러 피의 핵심 이론
오일러 피 함수의 원리는 에라토스테네스이 체와 비슷하다.
오일러 피 함수의 원리
- 구하고자 하는 오일러 피의 범위만큼 배열을 초기화한다.
- 2부터 시작해 현재 배열의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행한다(i는 K의 배수).
- 배열의 끝까지 2를 반복하여 오일러 피 함수를 완성한다.
오일러 피 함수 원리 이해하기
1 구하고자 하는 범위까지 배열을 생성한 후 2를 선택한다.
2 2의 모든 배수마다 P[i] = P[i] / 2 연산을 수행해 값을 갱신한다.
에라토스테네스의 채의 소수의 배수 지우기 부분을 P[i] = P[i] / K로 변경한 것이 된다.
3 배열이 끝날 때까지 반복한다.
- Do it! 알고리즘 코딩테스트 자바 편
