오일러피 - 백준 11689 : GCD(n, k)

 11689 : GCD(n, k)

문제

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

 

입력

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

 

출력

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

입력	출력
1	1
5	4
45	24

 

문제 풀이

• 오일러피로 푸는 문젠데 강의에 나온 이론으로 풀면 자꾸 런타임에러나는거;;

 

💡 오일러 피 구하는 다른 방법 - 소인수분해 사용

1.  N 에서 소인수를 찾아내고 𝝓(n) 값을 갱신한다.
2. 소인수의 배수를 제거하여 N을 점점 작게 만든다.
3. N이 소수로 남아잇다면, 𝝓(n) 값을 최종적으로 갱신한다.

(예시)

1. N = 36, res = 36
2. 소인수 확인 및 처리(N%i==0 확인, N까지 해당 소인수의 배수 다 빼기)
   1. i=2
      36%2==0 즉, i=2는 소인수이다
          res = res - (res/i) = 36 - (36/2) = 18
          N에서 2의 배수를 제거
          N = 36/2 = 18
          N = 18/2 = 9
   2. i=3
      9%3==0 즉, i=3는 소인수이다.
      res = res - (res/i) = 18 - (18/3) = 12
      N에서 3의 배수를 제거
      N = 9/3 = 3
      N = 3/3 = 1
   3. N=1, 더이상 소인수가 없으므로 반복 종료
   4. 만약 N이 소수로 남아있으면 
      res = res - (res / N);
   5. res 출력

 

실행 코드

import java.util.Scanner;

public class P11689_EulersPhi {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long res=N;

        for(int i=2;i<=Math.sqrt(N);i++) {
            if(N%i==0){ //i가 N의 소인수인지 확인
                res = res - (res/i); // 결과 갱신
                while(N%i==0){ // n에서 i의 배수 제거
                    N /= i;
                }
            }
            if(i>Math.sqrt(N)) break;
        }

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

        System.out.println(res);
    }
}