오일러 피 함수란?
- 양의 정수 N에 대해서, N보다 작거나 같은 양의 정수 중에서 N과 서로소인 정수의 개수를 나타낸다. 보통 𝜙(𝑛) 또는 𝜑(𝑛)로 표기한다.
- 즉, 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.
*오일러 피 함수는 증명을 통해서 완벽하게 알 수 있지만 여기서는 코딩테스트를 위한 내용만 다루려 한다.
에라토스테네스의 체
오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.
원리
1. 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스값으로 초기화한다.
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행한다. (i는 K의 배수)
3.배열의 끝까지 2번을 반복해서 오일러 피 함수를 완성한다.
EX) 1부터 15까지 수열에서 15와 서로소인 수 찾기
1. 2에 대해서 P[i] = P[i] - P[i]/K 연산을 수행한다. 여기서 K는 2이다.
2. 다음으로 3으로 이동해 3의 배수에 해당하는 값에 대해서도 P[i] = P[i] - P[i]/K 연산을 수행한다. 연산 후 결과는 밑과 같다. (k=3)
예를 들어서
P[6]은 3이었으므로 P[6] = 3 - (3/3) = 2 가 된다.
P[9] = 9 - (9/3) = 6 이 된다.
3. 배열이 끝날 때까지 반복한다.
여기서 각 인덱스에 해당하는 값들은 인덱스 값과 서로소인 인덱스 값 이하의 수의 개수를 말한다.
즉, 𝜙(8) = 4(1, 3, 5, 7) 이고 𝜙(11)=10(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)이다.
결론적으로 P[i] = P[i] - P[i]/K 의 과정은 N의 약수의 배수를 N 이하의 수들에 대해서 제거하는 과정이다.
2의 배수로 인한 탈락 - > 𝜙(6) = 6 - (6/2) = 3(1, 3, 5)
3의 배수로 인한 탈락 - > 𝜙(6) = 3 - (3/3) = 2(1, 5)
*Do it! 알고리즘 코딩테스트 책 참고*