유클리드 호제법 (최대 공약수, 최소 공배수)

E woo·2023년 7월 7일

알고리즘

개발 일기

목록 보기

13/15

유클리드 호제법

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

두 수의 최대공약수를 구하는 알고리즘으로 호제법은 두 수가 서로 상대방 수를
나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다.

과정

a > b 를 만족하는 a, b 가 있다고 가정했을 때 나머지 연산으로 몫 Q와 나머지 R 을 구할 수 있다.

a MOD b = Q...R
b MOD R = Q'...R'
R MOD R' = Q''...R''
R'' 이 0이 나온다면 R' 이 최대 공약수가 된다.

으로 결국 큰 수에서 작은 수로 나머지 연산을 한 후 나온 나머지를
작은 수로 나머지 연산 과정을 반복하여 0이 나올 때의 작은 수가 a, b의 최대 공약수가 된다.

예시

36 과 21의 최대 공약수를 구하시오.

36 % 21 = 1...15
21 % 15 = 1...6
15 % 6 = 2..3
6 % 3 = 2...0

36 과 21의 최대 공약수는 3 이 된다.

최소 공배수

최소 공배수는 소인수 분해를 통해 구할 수 있다는 사실을 알고 있다.
이때 소인수 분해는 두 수를 어떠한 수를 나누며 두 수 모두 소수가 나온 경우에

지금까지 나눈 수와 소수 2개를 곱해서 구할 수 있다.

두 수가 소수가 나오도록 나눌 수 있는 제일 큰 수는 결국 최대 공약수이다.

이를 가정하고 아래의 식을 보면

a와 b의 최대 공약수를 G 라고 했을 때

a = G * I
b = G * J

I 와 J 는 각각 최대 공약수로 나눈 소수로 가정할 수 있고 a 와 b 의 곱은

a * b = G * G * I * J

로 표현할 수 있다. 여기서 G 는 최대 공약수로 가정했기 때문에
G * I * J 는 위에서 얘기했던 대로 최소 공배수가 된다.

따라서 최소 공배수 lcm 은

lcm = a * b / gcb(a, b) {a > b 일 때}

로 구할 수 있다.

예제

36 과 21 의 최대 공약수는 3 이므로

36 * 21 = 3 * 최소 공배수 가 되어

최소 공배수는 252 가 된다.

구현

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

int main()
{
	int a, b;
    cin >> a >> b;
    
    cout << "두 수의 최대 공약수 gcd 는 : " << gcd(a, b);
    cout << "두 수의 최소 공배수 lcm 는 : " << (a * b) / gcd(a, b);
    
    return 0;

}