[GDG - 스터디] 오일러피 함수를 이용하여 GCD 구하기

오일러피 함수

• [ ] 오일러피 함수는 1부터 n까지의 정수 중에서 n과 서로소인 정수의 개수를 구하는 함수이다. ( ex: n = 9 일 때, 1부터 9 사이에서 9와 서로소인 정수는 1, 2, 4, 5, 7, 8로 총 6개이다. )

$$  \phi(9) = 6 $$

n이 소수인 경우

$$   \phi(n) = n - 1  $$

n이 소수가 아닌 경우(일반적인 경우)

• 소인수(p1, p2, … , pk) 분해를 사용하여 계산 가능하다 !

$$

\phi(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \dots \times \left(1 - \frac{1}{p_k}\right) $$

• [ ] 코드로 구현하면 다음과 같다.

public class EulerTotientFunction {
    // 오일러 피 함수 구현
    public static int phi(int n) {
        int result = n; // 초기값은 n으로 설정
        for (int i = 2; i * i <= n; i++) {
            // n이 i로 나누어 떨어지면 i는 n의 소인수
            if (n % i == 0) {
                // 중복된 소인수를 제거
                while (n % i == 0) {
                    n /= i;
                }
                // 결과값을 소인수만큼 줄임
                result -= result / i; // = (n - n * 1/p)
            }
        }
        // 남은 소인수가 있을 경우
        if (n > 1) {
            result -= result / n;
        }
        return result;
    }
	 ...
}

알고리즘 문제: GCD(n, k) = 1

• [ ] 오일러피 함수를 이용하여 n의 최대공약수를 구하는 문제이다.

 

실패 코드

• [ ] 1부터 n까지의 숫자 중에 오일러함수를 이용해서 최대공약수의 개수가 1개인 수들의 개수를 찾으면 되는 문제이다. → 하지만 런타임 에러가 발생했다..!!

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

public class Main {
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.print(eulerphi(n));
    }
    
    public static int eulerphi(int n) {
        int count = n;  // 최대 공약수가 한 개인 수들의 개수
        for (int i = 2; i <= Math.sqrt(n); ++i) {
            if (n % i == 0) {
                while (n % i == 0) {
                    n /= i;
                }
                count -= count / i;
            }
        }
        
        if (n > 1) {
            count -= count / n;
        }
        
        return count;
    }
}

---

해결 코드

• [ ] 런타임 에러가 발생한 이유는 단순하게 문제에서 제시한 입력값(n)의 크기가 int 범위보다 크기 때문이었다 !

$$ 1 \leq n \leq 10^{12} $$

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

public class Main {
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        System.out.print(eulerphi(n));
    }
    
    public static long eulerphi(long n) {
        long count = n;  // 최대 공약수가 한 개인 수들의 개수
        for (int i = 2; i <= Math.sqrt(n); ++i) {
            if (n % i == 0) {
                while (n % i == 0) {
                    n /= i;
                }
                count -= count / i;
            }
        }
        
        if (n > 1) {
            count -= count / n;
        }
        
        return count;
    }
}

 

https://thin-azimuth-2a9.notion.site/GCD-139f4ee21c0080e6808ecde89a6df664?pvs=4

오일러피 함수를 이용하여 GCD 구하기 | Notion