문제 설명

문제 분석

슈도코드

구현

public class 오일러_피_11689 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong(); // 소인수
        long cnt = n; // 서로소의 개수
        for (long p = 2; p <= Math.sqrt(n); p++) {
            if (n % p == 0) { // p가 소수인지 확인
                cnt = cnt - cnt / p;
                while (n % p == 0) { // 2^7 * 11이면 2^7을 없애고 11만 남김
                    n /= p;
                }
            }
        }
        // 소인수 구성이 남았을 때. 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락될 수 있다.
        if (n > 1) {
            cnt = cnt - cnt / n;
        }

        System.out.println(cnt);
    }
}