[알고리즘] 오일러 피

오일러 피

---

오일러의 피 함수는 𝜙(𝑁) 또는 P[N] 으로 표시되며, 자연수 N 이하의 양의 정수 중에서 
N과 서로소인 수의 개수를 나타내는 함수입니다. 두 수가 서로소라는 것은 공약수가 1 뿐인 경우를 말합니다.

 

오일러 피 알고리즘

---

1. '2' 부터 구하고자 하는 값의 제곱근까지의 소인수를 구합니다.
2. 결괏값을 갱신합니다.
3. N값에서 소인수를 나눠줍니다.
4. 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 은 서로소 개수 입니다. 증명은 생략하겠습니다.