정수론 - 오일러 피

오일러 피

오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있지만 여기서는 실제 코딩 테스트에 사용하기 위한 구현 부분만 알아본다.

 

 

오일러 피의 핵심 이론

오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.

1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화한다.
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면 (=소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] / K 연산을 수행한다. (i는 K의 배수)
3. 배열의 끝까지 2를 반복하며 오일러 피 함수를 완성한다.

 

 

오일러 피 함수의 원리 이해하기

 

1. 구하고자 하는 범위까지 배열을 생성한 후 2를 선택한다.

 

2. 2의 모든 배수마다 P[i] = P[i] - P[i] / 2 연산을 수행해 값을 갱신한다. 예를 들어 8 = 8 - (8 / 2)를 통해 4를 계산한다. 

 

3. 소수 구하기에서 배수를 지우는 부분만 P[i] = P[i] - P[i] / K로 변경하면 오일러 피 함수를 간단히 구현할 수 있다. 탐색을 계속 진행하면서 N = ∮(N)인 곳(소수)을 찾아 값을 갱신한다. (소인수 : 소수인 약수)

 

4. 배열이 끝날 때까지 반복한다.

 

 

초반 인덱스 6의 값은 6이었다. 2의 모든 배수마다 P[i] = P[i] - P[i] / K로 변경할 때 [6] = 6 - 6 / 2, 즉 3이 되고 이는 2의 배수인 2, 4, 6이 지워졌다는 뜻이다. 2, 4, 6은 모두 약수로 2를 가지고 있기 때문에 6과 서로소가 될 수 없기 때문이다. 현재 인덱스 6의 값은 3으로, 6 이하 서로소의 개수가 3개라는 뜻이다.

그리고 i가 하나 증가하며 3이 됐을 때 다시 P[i] = P[i] - P[i] / K를 진행하며 [6] = 3 - 3 / 3 이 되어 2가 되는데, 이는 3을 약수로 갖고 있는, 즉 3의 배수가 되는 숫자를 지웠다는 뜻이다. 6이하 3의 배수는 3과 6이 있는데 왜 하나만 지워졌나면 앞에서 2의 배수를 지울 때 이미 숫자 6이 지워졌기 때문이다. 그렇게 끝까지 돌고 난 후 인덱스 6의 값은 최종적으로 2가 되며, 이는 즉 6 이하의 숫자들 중 서로소가 되는 개수가 2개 (1과 5)라는 뜻이다. 

 

오일러 피를 구하는 문제가 출제되는 빈도는 높지 않다. 하지만 원리를 알지 못하면 출제 됐을 때 문제 자체에 접근하기 어렵다.

 

---

 

[백준 11689번] GCD(n, k) = 1

https://www.acmicpc.net/problem/11689

 

문제에서 요구하는 GCD(n, k) = 1을 만족하는 자연수의 개수가 바로 오일러 피 함수의 정의이다. 즉, 오일러 피 함수를 잘 구현할 수 있는지 묻는 문제이다. 

 

1. 서로소의 개수를 표현하는 변수 result와 현재 소인수 구성을 표시하는 변수 n을 선언한다. 예제 입력 4의 겨우 변수 초기화는 n = 45, result = 45로 한다.

 

2. 오일러 피 핵심 이론 부분을 참고해 2 ~ N의 제곱근까지 탐색하면서 소인수일 때 result = result - (result / 소인수) 연산으로 result 값을 업데이트한다. 이때 n에서 이 소인수는 나누기 연산으로 삭제한다. 

- P(현재 수) = 2 => n(45) % P(2) != 0 => 소인수가 아님
- P(현재 수) = 3 => n(45) % P(3) == 0 => 소인수이므로 값 업데이트
   => result = 45 - 45 / 3 = 30
   => n = 3 ^ 2 x 5 = 5
- P(현재 수) = 4 => 현재 n(5)의 제곱근보다 4가 크므로 반복문 종료

 

3. 반복문 종료 후 현재 n이 1보다 크면 n이 마지막 소인수라는 뜻이다. result = result - (result / n) 연산으로 result 값을 마지막으로 업데이트한 후 출력한다.

result(30) = 30 - (30 / 5) = 24

 

 

 

[정답]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        /*
        p: 현재 수
        n : 소인수 구성
        result : 서로소 개수
         */
        long n = Long.parseLong(br.readLine());
        long result = n;
        for (long p = 2; p <= Math.sqrt(n); p++) {   // 제곱근까지만 진행하기
            if (n % p == 0) {                       // p가 소인수인지 확인하기
                result = result - result / p;       // 결괏값 업데이트하기
                while (n % p == 0) {                // 2^7 * 11이라면 2^7을 없애고 11만 남김
                    n /= p;
                }
            }
        }
        if (n > 1)                                  // 아직 소인수 구성이 남아 있을 때
            // 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락되는 케이스
            result = result - result / n;
        System.out.println(result);
    }
}

 

45라 가정했을 때 n과 result는 45, p는 2부터 시작한다. (45 = 3^2 x 5) 2로 나눴을 때 나머지가 0이 아니라는 것은 소인수가 아니라는 뜻이다. 3으로 나누니 나누어 떨어지므로 소인수라는 뜻, P[i] = P[i] - P[i] / K 연산을 수행한다. result = 45 - 45 / 3 = 30. 3의 배수를 전부 빼준 것이다. 그 다음 소인수를 구해야 하므로 n (45)에 현재 소인수인 3을 나누어 떨어지지 않을 때까지 계속 나누어준다. 소인수 3이 하나만 있는게 아닌 여러 개 있을 수 있기 때문이다. (3^2 x 5 의 3^2 부분 처리) 45 / 3 = 15 / 3 = 5로 n은 5가 되며, 45의 소인수인 3 다음 소인수는 5가 되었다는 의미가 된다. 5를 3으로 나누면 2가 남으므로 나누지 않고 반복문을 빠져나가며 p는 3이 되고 n은 5가 되었다. 3이 5의 제곱근인 2보다 크므로 for 루프를 빠져나가고 (계산수를 줄이기 위해), n이 1이 아니라는 것은 위에서 n을 p로 나누는 과정 중 끝까지 나누지 못한 소인수가 아직 하나 남아있다는 의미이다. 그러므로 그 하나의 소인수를 처리하기 위해 마지막 P[i] = P[i] - P[i] / K 연산을 수행하면 답을 구할 수 있다.

 

원래는 배열을 처음부터 끝까지 만들어서 모든 서로소의 개수를 구했지만 여기서는 N의 범위가 10^12나 되므로 해당 N의 서로소 개수만을 구체적으로 구했다. 또한 제곱근까지만 진행을 해서 계산의 수를 줄였다.

 

 

 

 

 

 

[참고 자료]

- Do it! 알고리즘 코딩 테스트 자바편