041 : Euler phi

(Briefing)
문제	단 하나의 맥락	입출력과 되어야 하는 그림
GCD(n, k) = 1(1<= k <=n) 를 만족하는 자연수 n의 갯수를 출력하라		I // n(1 <= n <= 10^12) O // 갯수

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        
        // Input Supply Cable
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        
        // Preprocessing
        long result = n;
        
        // Operating Euler phi function
        for (long p = 2; p <= Math.sqrt(n); p++) {
            if (n % p == 0) {
                result = result - result/p;
                while (n % p == 0) {
                    n /= p;
                }
            }
        }
        if (n > 1)
            result = result - result/n;

        // Output Extracting Cable
        System.out.println(result);

    }
}