[11689] GCD(n, k) = 1 (JAVA)

# 문제 설명

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다.

---

출력

GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.

 

# 정답 코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long N = Long.parseLong(st.nextToken());
        long result = N;

        //GCD(n,k) = 1을 만족하는 자연수 = N과 서로소인 수
        for (int k = 2; k <= Math.sqrt(N); k++) {
            //k가 n의 소인수인 경우
            if (N % k == 0) {
                result -= result / k;

                while (N % k == 0) {
                    N /= k;
                }
            }
        }

        if (N > 1) {
            result -= result / N;
        }

        System.out.print(result);
    }
}

 

자연수 N을 입력받는다.

n과 k의 최대 공약수가 1인 수는 다른 말로 하면 N과 서로소인 수를 의미한다.

오일러 피 함수를 이용하여 N과 서로소인 수의 개수를 구한다.

 

2부터 N의 제곱근까지 k를 순회한다.

만약 k가 n의 소인수인 경우, result에 result / k를 빼주고 N의 소인수에서 k를 제거한다.

 

반복이 끝난 후 만약 N이 1보다 크면, result에 result / k를 빼준다.

이는 for문이 N의 제곱근까지만 반복하기 때문에 N에 소인수가 남아있을 수 있어 수행해준다.