My Notes

분수 결과값을 기약분수로 만드는 문제에서 최대공약수를 구하는 알고리즘이 필요했다.

아래는 유클리드 호제법을 이용하여 최대공약수를 구하는 메서드이다.

* 유클리드 호제법(Euclidean algorithm)이란?

두 수의 최대공약수(GCD)를 빠르게 구하는 고대 그리스 수학자 유클리드가 고안한 알고리즘이다.

두 정수 a와 b(단, a > b)가 있을 때, a와 b의 최대공약수(GCD)는 b와 a % b의 최대공약수와 같다는 원리를 반복적으로 이용한다.

// 1. 재귀함수 사용
public static int gcd1(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 2. 반복문 사용
public static int gcd2(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}