오일러 피
오일러의 피 함수는 𝜙(𝑁) 또는 P[N] 으로 표시되며, 자연수 N 이하의 양의 정수 중에서
N과 서로소인 수의 개수를 나타내는 함수입니다. 두 수가 서로소라는 것은 공약수가 1 뿐인 경우를 말합니다.
오일러 피 알고리즘
- '2' 부터 구하고자 하는 값의 제곱근까지의 소인수를 구합니다.
- 결괏값을 갱신합니다.
- N값에서 소인수를 나눠줍니다.
- N이 1보다 크면 결괏값을 최종 조정합니다.
오일러 피 구현
int N; // 구하고자 하는 수
int result = N;
for (int k = 2; k <= Math.sqrt(N); k++) {
if (N % k == 0) { // k가 소인수인지 확인
result -= result / k; // 결과값 업데이트
while (N % k == 0) { // N에서 소인수 없애기
N /= k;
}
}
}
if (N > 1) { // 소인수가 남아있을 때
result -= result / N;
}
오일러 피 시간복잡도
오일러 피의 시간복잡도는 O(Φn logn)입니다. 여기서 Φn 은 서로소 개수 입니다. 증명은 생략하겠습니다.
'CS > 알고리즘' 카테고리의 다른 글
[알고리즘] 라빈-카프 알고리즘 (0) | 2024.08.29 |
---|---|
[알고리즘] 다익스트라 (0) | 2024.07.31 |
[알고리즘] 소수 구하기 (0) | 2024.06.18 |
[알고리즘] LCM (0) | 2024.06.13 |
[알고리즘] GCD - 유클리드 호제법 (0) | 2024.06.12 |