백준 11689 GCD(n, k) = 1

문제

풀이

public class Q11689_오일러피 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 서로소 후보의 개수
        long n = sc.nextLong();
        // 서로소의 개수
        long result = n;
        // 제곱근까지 탐색
        for (long i = 2; i <= Math.sqrt(n); i++) {
            // 현재 인덱스가 n의 소인수라면
            if (n % i == 0) {
                // 배열에서 현재 인덱스의 배수 값들을 제거
                // 예를 들어 처음 기준 값이 30이라고 했을 때
                // i가 2일때 해당 반복에서 2의 배수 값들은 모두 제거됨 2,4,6,8,10,12,14,16,18,20,22,24,26,28,30
                // result = 30 - 30 / 2 = 15 -> 서로소 후보개수 = 15개 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29

                // i가 3일때 3,9,15,21,27
                // result = 15 - 15/3 = 10 -> 서로소 후보개수 = 10개 1,5,7,11,13,17,19,23,25,29

                // i가 4일때 5는 나누어 떨어지지 않으므로 다음 반복문 실행

                // i가 5일때 5, 25 -> Math.sqrt(30) = 5이므로 마지막 반복
                // result = 10 - 10/5 = 8 -> 서로소 후보개수 = 8개 1,7,11,13,17,19,23,29
                result = result - result / i;
                // 기준값을 변경
                // 그 이유는 중복 제거를 방지하기 위해서이다.
                // 이미 i가 2일때 서로소가 아닌 수를 한번 제거한 상태로 서로소 후보의 개수는 15개가 된다.
                // 따라서 다음 반복문에서 서로소 후보의 개수는 30이 아닌 15가 되어야 한다.
                // 그 다음은 5
                // 그 다음은 1
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        // 현재 n은 1이므로 실행X
        if (n > 1) {
            result = result - result / n;
        }
        // 결과 = 8
        System.out.println(result);
    }
}

리뷰

오일러 피를 활용하는 문제였다.
오일러 피 함수는 1~n까지의 범위에서 n과 서로소인 자연수의 개수를 찾는다.

1. 2부터 인덱스를 시작하여 현재 인덱스가 n의 소인수라면 해당 인덱스의 배수값들을 모두 제거한다.

   • 다른 말로 하면 서로소가 아닌 값들을 제거한다.
   • 이와 함께 서로소의 개수를 계산한다.
     result = result - result / i(현재 인덱스)

2. 1번에서 서로소가 아닌 값들을 제거했으므로 소인수분해를 통해 서로소후보의 개수를 재설정한다.

3. 1번과 2번을 기존에 주어진 수 n의 제곱근까지 반복한다.

4. 만약 서로소후보의 개수가 1보다 크다면 현재 n이 마지막 소인수라는 뜻이므로 서로소의 개수를 마지막으로 계산해준다.

공식만 암기하고 넘어가고 싶지 않아 흐름을 이해하려고 하다보니 또 시간이 오래걸렸다ㅜ