BOJ_11689 : GCD(n, k) = 1

👉 문제링크

11689번: GCD(n, k) = 1

---

---

🔸 문제 분석 🔸

• 1부터 자연수 n까지의 범위에서, 최대공약수(GCD)가 1인 자연수의 개수를 구하는 문제이다.
• 다시 말하면 서로소의 개수를 구하는 문제이다.

🔸 문제 풀이 🔸

• 서로소 개수를 구하는 공식으로 오일러의 피 함수(Euler product formula; 오일러 곱 공식)을 사용한다.
  • n의 소인수로 P[i] = P[i] - P[i]/K (i는 K의 배수) 연산을 반복한다.
• n이 소수이거나, n이 지수가 1인 소인수를 가지는 경우, 오일러 피 함수를 1회 더 적용한다.

🔸 코드 🔸

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long n = Long.parseLong(br.readLine());
        long result = n;

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                result -= result / i;
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 1)
            result -= result / n;
        bw.write(Long.toString(result));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• n은 현재 소인수의 구성을 표시하고, result는 서로소의 개수를 표시한다.
• 2부터 n의 제곱근 까지 탐색하면서 소인수일 때 오일러 피 연산 result = result - (result/소인수) 으로 result를 업데이트한다.
  • n에서 해당 소인수는 나누기 연산으로 삭제한다. ( 소인수가 3일 때, 3^2 x 5 => 5)
• 반복문을 종료하고  n이 1보다 크면, n이 마지막 소인수라는 뜻이다.
  • n이 소수거나, n이 지수가 1인 소인수를 가질 때 이므로 오일러 피 연산을 1회 더 적용한다.

---

🔸 end 🔸

• 오일러 피 연산에 대해 공부하고 예시 문제로 풀어보았다. 처음엔 에라토스테네스의 체와 비슷하게 구현할 수 있다고 배워서 배열을 만들어 계산했다.
  • p[n]만 구하면 되는데 불필요한 계산이 많아지는가 싶었는데, 입력이 long으로 받아야 해서 런타임 에러가 났다.
  • 알아보니 배열을 선언하는게 아니라, 서로소 결과값 result와 소인수 구성 n의 두 가지 변수로 계산하는 것이었다.
  • n이 나타내는 소인수 구성이라는 말이 이해가 잘 안됐었는데, 2부터 n의 제곱근까지 차례로 나누어 떨어지자마자 제외시키니까 i가 그냥 인수가 아니라, 소인수가 된다는걸 겨우 이해했다.
• 정수론 문제는 참 어렵지만 새로운 계산 방식을 배울 수 있는 값진 경험이었다.