[알고리즘] 코테 유형 분석 27. 오일러 피 함수

안녕하세요 오늘은 오일러 피 함수에 대해 포스팅해보겠습니다. 오일러 피 함수 P[N]이란 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 구하는 함수입니다. 오일러 피 함수는 에라토스테네스의 체에서 배수를 지우는 부분만 P[i] = P[i] - P[i]/K로 치환하는 방식으로 구현할 수 있습니다. 다음은 구현 방법입니다.

1. 구하고자 하는 오일러 피의 범위만큼 배열 초기화
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하여 P[i] = P[i] - P[i]/K 수행
3. 배열의 끝까지 2번을 반복하여 오일러 피 함수 완성

백준 11689(GCD(n,k) = 1) 문제를 통해 오일러 피 함수를 구현해보겠습니다. 자연수 N이 주어졌을 때 n과 k의 최대공약수가 1을 만족하는 자연수 개수를 구하는 프로그램을 구현하는 문제입니다. 이 문제 자체가 오일러 피 함수의 정의이기 때문에 오일러 피 함수를 구현합니다. 입력 범위가 long이기 때문에 배열을 구현해서 에라토스테네스의 체를 사용하지 않고 구하고자 하는 결과값 P[N]을 N으로 초기화한 후 2부터 N의 제곱근까지 K의 숫자로 탐색하여 N과 k가 서로소가 아닐 경우 res = res - res/k로 처리하고 N과 k가 서로소가 될 때까지 나누어줍니다. N이 1보다 크다면 res = res - res/k 연산을 한번 더 수행한 후 결과를 출력합니다.

import java.util.*;
import java.io.*;

class Main{
    static long N;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Long.parseLong(br.readLine());
        long res = N;
        for(long k=2;k<=Math.sqrt(N);k++){
            if(N%k == 0){
                res = res - res/k;
                while(N%k == 0) N /= k;
            }
        }

        if(N>1) res = res - res/N;
        System.out.println(res);
    }
}