[코딩테스트] 백준 11689 자바

백준 11689

백준 11689 문제

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

import java.util.*;

public class Boj11689 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(); // 어떤 수
        long result = n; // 결괏값

        for (int i = 2; i <= Math.sqrt(n); i++) { // 2부터 n의 제곱근까지 반복
            if (n % i == 0) { // 현재 값이 소인수라면
                result -= result / i; // 결괏값 = 결괏값 - 결괏값 / 현재값
            }

            // n에서 현재 소인수 내역을 제거
            while (n % i == 0) {
                n /= i;
            }
        }

        if (n > 1) { // n이 마지막 소인수일 때
            // 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락되는 케이스
            result -= result / n; // 결괏값 = 결괏값 - 결괏값 / 현재값
        }

        System.out.println(result); // 결괏값 출력
    }
}

풀이

1. 어떤 수를 입력 받아 n에 저장한다.
2. 결괏값 result에 n을 저장한다.
3. 2부터 n의 제곱근까지 반복한다.
   3-1. 현재값 i가 n의 소인수라면, 결괏값 = 결괏값 - 결괏값 / 현재값으로 결괏값을 업데이트한다.
   3-2. n에서 현재 소인수 내역을 제거하기 위해 n을 현재값 i로 나눌 수 있을 때까지 나눈다.
4. 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락될 수 있기 때문에 n이 1보다 크다면(n이 마지막 소인수일 때) 한 번 더 결괏값 = 결괏값 - 결괏값 / 현재값으로 결괏값을 업데이트한다.
5. 결괏값을 출력한다.