[Do It! 코딩테스트 자바편(김종관)] 문제 041(백준 11689번)

난이도

• 교재 이론 설명이 처음 볼 때 부실해서 코드하고 교재 이론 설명하고 번갈아 봐서 겨우 어느 정도 이해했다. 문제 풀이는 뒷전이 된 것 같다. 이해하는 데에 시간이 꽤 많이 걸렸다.
• 교재처럼 Math.sqrt를 활용 안 해서 그런지 시간초과라는 결과를 얻었다.

문제

오일러 피 함수 구현하기(백준: 11689번)

풀이

• 책에 오일러 피 함수 원리와 코드 이해한 것을 메모해 놓았다. 복습할 때 교재 기록 참고할 것!
• GCD란?
  • 최대공약수(Greatest Common Divisor, GCD)
  • GCD(n, k) = 1의 뜻은 두 수 n과 k의 최대공약수가 1이라는 뜻. 즉 두 수는 서로소이다.
  • 서로소: 공약수가 1뿐인 두 정수

import java.io.*;
public class P11689_GCDNK1 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    long n = Long.parseLong(br.readLine());
    long result = n;
    for (long p = 2; p <= Math.sqrt(n); p++) { // 제곱근까지만 진행
      if (n % p == 0) { // p가 소인수인지 확인
        result = result - result / p; // 결과 값 업데이트
        while (n % p == 0) { // 해당 소인수를 지워줌 2^7*11이라면 2^7을 없애고 11만 남김
          n /= p;
        }
      }
    }
    if (n > 1) // 아직 소인수 구성이 남아있는 경우
//(반복문에서 제곱근까지만 탐색했기 때문에 1개의 소인수가 누락되는 케이스)
      result = result - result / n;
    System.out.println(result);
  }
}