[Java]유클리드 호제법, 최대공약수, 최소공배수

유클리드 호제법은 두 양의 정수, 혹은 다항식의 최대공약수를 구하는 알고리즘이다.

기원전 300년에 그리스의 수학자 유클리드에 의해 기술된 이 알고리즘은

인류 최초의 알고리즘이라는 호칭도 가지고 있다.

그 내용은 다음과 같다.

유클리드 호제법

두 양의 정수 a, b(a > b)에 대하여 a = bq + r (0 ≤ r < b)이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다. 즉,

gcd(a, b) = gcd(b, r)이다.

이때 r = 0이라면, a, b의 최대공약수는 b가 된다.

쉽게 말하면 큰 숫자를 작은 숫자로 나누고, 그 나머지로 작은 숫자를 나누는 계산을 나머지가 0이 될 때까지 반복하는 것이다.

예를 들어 1096과 411의 최대공약수를 구한다고 해보자. 첫 계산은 다음과 같다.

1096 % 411 = 274 // 나머지 연산

두 번째 계산은 작은 숫자를 나머지로 나누는 것이다.

411 % 274 = 137

이 과정을 나머지가 0이 될 때까지 반복한다.

274 % 137 = 0

나머지가 0이 나오면, 마지막으로 나눠준 작은 숫자가 1096과 411의 최대공약수가 된다.

이 경우 시간 복잡도는 O(log n)이다.

먼저 반복문으로 구현해 보자.

import java.util.Scanner;

public class Euclidean {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("두 수를 입력하시오.");
        a = sc.nextInt();
        b = sc.nextInt();

        int result = gcd(a, b);
        System.out.println("최대공약수: " + result);
        System.out.println("최소공배수: " + a * b / result);
    }

    static int a, b;

    public static int gcd(int a, int b) {
        int gcd = 0;
        while (b > 0) {
            gcd = a % b;
            a = b;
            b = gcd;
        }
        return a;
    }
}

계속해서 재귀를 이용해 구현하는 방법이다.

import java.util.Scanner;

public class Euclidean {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("두 수를 입력하시오.");
        a = sc.nextInt();
        b = sc.nextInt();

        int result = gcd(a, b);
        System.out.println("최대공약수: " + result);
        System.out.println("최소공배수: " + a * b / result);
    }

    static int a, b;

    public static int gcd(int a, int b) {
        if(a%b == 0) return b;
        return gcd(b, a%b);
    }
}

시간 복잡도는 비슷하지만 재귀의 경우 공간 복잡도가 늘어나기 때문에 불리하다고 한다.