최대공약수와 최소공배수 · 알고리즘 노트

개념

두 자연수를 모두 나누어떨어지게 하는 가장 큰 수가 최대공약수(GCD)입니다. 두 수의 공통 배수 중 가장 작은 자연수가 최소공배수(LCM)입니다.

$24$ 개와 $18$ 개를 각각 같은 크기의 묶음으로 남김없이 나누려면, 묶음의 크기는 두 수의 공약수여야 합니다. 가장 큰 묶음의 크기가 최대공약수입니다. $24$ 번마다 일어나는 일과 $18$ 번마다 일어나는 일이 동시에 다시 일어나는 주기를 구할 때는 최소공배수를 사용합니다.

유클리드 호제법

큰 수를 작은 수로 나눈 나머지로 문제를 줄입니다. $a$ 를 $b$ 로 나눈 몫이 $q$ , 나머지가 $r$ 이면 $a=bq+r$ 입니다.

$a$ 와 $b$ 의 공약수는 $a-bq=r$ 도 나눕니다.
반대로 $b$ 와 $r$ 의 공약수는 $bq+r=a$ 도 나눕니다.

따라서 $(a,b)$ 와 $(b,r)$ 의 공약수가 같으므로 $\gcd(a,b)=\gcd(b,a\bmod b)$ 입니다. 이 변환을 반복하면 나머지가 점점 작아집니다. 나머지가 $0$ 이 되면 앞의 수가 뒤의 수로 나누어떨어지므로 마지막으로 나눈 수가 최대공약수입니다.

$24$ 와 $18$ 은 $24\bmod18=6$ , $18\bmod6=0$ 이므로 최대공약수가 $6$ 입니다.

최소공배수

최대공약수를 $g$ 라고 하면 $a=gx$ , $b=gy$ 로 나타낼 수 있습니다. 공통 인수를 모두 $g$ 로 꺼냈으므로 $x$ 와 $y$ 의 최대공약수는 $1$ 입니다. 두 수의 배수가 되려면 공통 부분 $g$ 와 나머지 인수 $x,y$ 를 모두 포함해야 하므로 최소공배수는 $gxy$ 입니다.

두 수를 그대로 곱한 $ab=g^2xy$ 에는 공통 부분 $g$ 가 한 번 더 들어 있습니다. 따라서 $g$ 로 한 번 나누면 됩니다.

$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$

$24=6\times4$ , $18=6\times3$ 이므로 최소공배수는 $6\times4\times3=72$ 입니다.

복잡도

입력한 두 자연수를 $a,b$ 라고 합니다.

연산	시간복잡도	추가 공간
반복 호제법·최소공배수	$O(\log\min(a,b))$	$O(1)$

예제

문제

두 양의 정수의 최대공약수와 최소공배수를 구하여라.

입력

첫째 줄에 두 양의 정수 $A,B$ 가 공백을 사이에 두고 주어진다. $1\le A,B\le1\,000$ 이다.

출력

최대공약수와 최소공배수를 공백으로 구분하여 출력한다.

예제 코드

C++20

#include <iostream>

using namespace std;

int main() {
    int a, b, x, y, r;

    cin >> a >> b;
    x = a;
    y = b;
    while (y != 0) {
        r = x % y;
        x = y;
        y = r;
    }

    cout << x << ' ' << a / x * b << '\n';
}

Java 17

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in;
        int a, b, x, y, r;

        in = new Scanner(System.in);
        a = in.nextInt();
        b = in.nextInt();
        x = a;
        y = b;
        while (y != 0) {
            r = x % y;
            x = y;
            y = r;
        }

        System.out.println(x + " " + a / x * b);
    }
}

Python 3

a, b = map(int, input().split())
x, y = a, b

while y != 0:
    x, y = y, x % y

print(x, a // x * b)

2.2.5 GCD & LCM

개념

유클리드 호제법

최소공배수

복잡도

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드