코딩 테스트 [정수론] - 오일러 피 함수 구현하기

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

(시간 제한 1초)

---

입력

1번째 줄에 자연수 n(1 ≤ n ≤ $10^{12}$)이 주어진다.

출력

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

예제 입력
45	// n

예제 출력
24

---

1단계 - 문제 분석하기

문제에서 요구하는 GCD(n, k) = 1 을 만족하는 자연수의 개수는 오일러 피의 함수의 정의이다.
즉, 오일러 피 함수를 구현할 수 있는지 묻는 문제이다.

2단계 - 손으로 풀어 보기

1 서로소의 개수를 표현하는 변수 result와 현재 소인수 구성을 표시하는 변수 n을 선언한다.
예제 입력의 경우 변수 초기화는 n = 45, result = 45 로 한다.

2 오일러 피 핵심 이론 부분을 참고해 2 ~ N의 제곱근까지 탐색하면서 소인수일 때 result = result - (result / 소인수) 연산으로 result 값을 업데이트한다. 이때 n에서 이 소인수는 나누기 연산으로 삭제한다.

· P(현재 수) = 2 ⇒ n(45) % P(2) != 0 ⇒ 소인수가 아님
· P(현재 수) = 3 ⇒ n(45) % P(3) == 0 ⇒ 소인수이므로 값 업데이트
⇒ result = 45 - 45 / 3 = 30
⇒ n = $3^2$ x 5 = 5
· P(현재 수) = 4 ⇒ 현재 n의 제곱근보다 4가 더 크므로 반복문 종료.

3 반복문 종료 후 n이 1보다 크면 n이 마지막 소인수라는 뜻이다. result = result - (result / n) 연산으로 result 값을 마지막으로 업데이트 한 후 출력한다.

※ result(30) = 30 - (30 / 5) = 24

3단계 - sudo코드 작성하기

n(소인수 표현) result(결괏값)

for(2 ~ n의 제곱근)
{
	if(현재 값이 소인수라면)
    {
    	결괏값 = 결괏값 - 결괏값 / 현재값
        n에서 현재 소인수 내역을 제거하기
    }
}

if(n > 1)	// n이 마지막 소인수일때
	결괏값 = 결괏값 - 결괏값 / n

결괎값 출력

4단계 - 코드 구현하기

import java.util.Scanner;

public class Q41 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long n = Long.parseLong(sc.next());
        long result = n;

        for(long p = 2; p <= Math.sqrt(n); p++){
            if(n % p == 0){
                result = result - result / p;

                while(n % p == 0){
                    n = n / p;
                }
            }
        }

        if(n > 1)
            result = result - result / n;

        System.out.println(result);
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편