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

백준 11689번 문제  - GCD(n, k) = 1

11689번: GCD(n, k) = 1

---

문제 분석

 

 

• 1부터 N까지 수 중에서 최대공약수가 1인 수의 개수를 출력해라
  • GCD(n,k) : n하고 k의 최대 공약수

---

해결 키 포인트

 

• 정수론 - 서로소 개수 : 오일러 피
• 메모리, 시간이 여유롭지 않다
  • 메모리: 배열로 값을 따로 저장하지 않고 푼다
  • 시간: N의 약수 이용한다 | N의 제곱근까지만 확인한다.
• 처음에 헷갈렸던 것
  • 1~1까지 최대 공약수 수는 왜 1인가?: 문제를 보면 N도 포함해서 최대공약수가 1인 수를 출력하는 것
    → 즉, 1이 입력되면 자기 자신과 1을 비교해 최대 공약수가 1인 수는 1개로 1 출력
  • 1~5까지 최대 공약수 수는 왜 4인가?
    : 5랑 5도 최대 공약수를 계산해줘야한다 (필자는 이를 따로 생각안하고 5랑 5의 최대공약수는 1인 걸로 착각함)
    → 즉, 5랑 5는 최대 공약수가 5이므로 5를 제외해 최대 공약수가 1인 수는 5를 제외한 (1,2,3,4)로 4 출력

 

---

오일러 피

1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻하며, 이 함수는 다음 알고리즘을 따른다.

 

오일러 피 알고리즘

 

1. 구하고자 하는 오일러 피의 범위만큼 1차원 배열 생성 ( P [] )

2. 2부터 시작해 N의 제곱근까지 해당 값의 배수마다 ( P[i] = P[i] - (P[i] / i ) ) 로 값 재 설정

3. 2~N의 제곱근 까지 탐색을 반복한 후 배열에서 index와 P[i] 값이 동일한 수들이 서로소

 

---

코드

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

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

        // N 입력
        long N = Long.parseLong(br.readLine());

        // 현재 N과 최대공약수가 1인 k 개수를 나타내는 count 값 초기화
        long count = N;

        // 제곱근까지만 반복
        for(long i = 2; i <= Math.sqrt(N); i++) {
            // N % i가 0일 경우, i는 N의 약수
            if(N % i == 0) {
                // N이하의 i가 약수인 다른 수들 개수를 빼기
                count -= count / i;
                // 지금 N값에서 해당 약수를 빼기 (중복 제거 발생 방지를 위해)
                while(N % i == 0) {
                    N /= i;
                }
            }
        }

        // 아직도 약수가 남아 있을 경우 한 번 더 빼서 count 마무리
        if(N > 1) {
            count -= count / N;
        }

        System.out.println(count);
    }
}