[Algorithm] 최대 공약수(GCD)와 최소 공배수(LCM) ; 유클리드 호제법(Euclidean Algorithm)

최대 공약수(GCD)와 최소 공배수(LCM) ; 유클리드 호제법(Euclidean Algorithm)

최대 공약수(GCD; Greatest Common Divisor(Factor))

• 두 개 이상의 자연수들의 공통인 약수들의 모임을 공약수(Common Divisor)라고 하고, 공약수 중에서 가장 큰 수를 최대 공약수(Greatest Common Divisor)라고 한다.
• 예) $12$의 약수는 $\{1, 2, 3, 4, 6, 12\}$ 이고 $18$의 약수는 $\{1, 2, 3, 6, 9, 18\}$일 때, 두 수 $12$와 $18$의 공약수는 $\{1, 2, 3, 6\}$이고 최대 공약수는 $6$이 된다.

 

코드

int gcd(int x, int y) {
    for (int i = (x > y ? y : x); i >= 1; i--) {    // 두 수의 최댓값부터 시작해서 1까지
        if (x % i == 0 && y % i == 0) {    // 두 수로 나누어 떨어질 경우
            return i;   
        }
    }
}

• 두 개의 정수 x와 y의 최대 공약수는 x와 y의 최솟값보다 클 수가 없기 때문에 for 문의 초기부 i는 두 개의 정수 x와 y 중에서 최솟값으로 초기화하고 초깃값부터 1까지 회전한다.
• 두 개의 정수 x와 y를 동시에 나눌 수 있는 첫 번째 정수가 두 수 x와 y의 가장 큰 공약수이므로, 첫 번째로 조건문을 만족하는 정수 i는 최대 공약수가 된다.

 

유클리드 알고리즘(Euclidean Algorithm) ; 유클리드 호제법

유클리드 (BC330? - BC275?)

• 유클리드 알고리즘(Euclidean Algorithm) 또는 유클리드 호제법은 2개의 자연수의 최대 공약수(GCD)를 구하는 알고리즘이다.
• 유클리드(Euclid, BC330? ~ BC275?)가 기원전 300년 경에 쓴 『원론』 제 7권에 나오는 가장 오래된 알고리즘이다.
  • "두 개의 자연수 A와 B에 대해서 A를 B로 나눈 나머지를 R이라고 하면(단, A ≥ B) A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다."
• 이 성질을 이용하여 B를 R로 나눈 나머지 R1을 구하고, 다시 R을 R1으로 나눈 나머지 R2를 구하고, 다시 R1을 R2로 나눈 나머지를 구하는 과정을 반복하다가 나머지가 0이 되었을 때 이 때 나누는 수 제수가 A와 B의 최대 공약수가 된다는 알고리즘이다.

 

그림으로 이해하기

• 8개의 상자가 놓여 있는 A 그룹과 3개의 상자가 놓여있는 B 그룹이 있을 때, 두 그룹 A와 B는 모두 1개의 상자의 배수이므로 두 그룹 A와 B의 최대 공약수는 1개의 상자가 된다.

• A와 B 그룹은 둘 다 최대 공약수가 1개의 상자이므로, 1개의 상자의 배수이다.
• A 그룹을 B 그룹으로 나눈 나머지는 2개의 상자가 나오고, 이 2개의 상자는 A 그룹에 있었던 상자이므로 나머지로 나온 2개의 상자도 최대 공약수인 1개의 상자의 배수가 된다.
• 다시 3개의 상자가 A 그룹이 되고, 나머지 2개의 상자가 B 그룹이 되어 같은 연산을 한다.

• A와 B 그룹은 둘 다 최대 공약수인 1개의 상자의 배수의 배수이다.
• A 그룹을 B 그룹으로 나눈 나머지는 1개의 상자가 나오고, 이 1개의 상자는 A 그룹에 있었던 상자이므로 나머지로 나온 1개의 상자도 최대 공약수인 1개의 상자의 배수가 된다.
• 다시 2개의 상자가 A 그룹이 되고, 나머지 1개의 상자가 B 그룹이 되어 같은 연산을 한다.

• A와 B 그룹은 둘 다 최대 공약수인 1개의 상자의 배수의 배수이다.
• A 그룹을 B 그룹으로 나누면 나머지는 0개의 상자가 나오고, B 그룹에 있던 1개의 상자가 지금까지 나누었던 모든 상자 그룹들을 나눌 수 있는 최대 상자이므로 마지막으로 남은 이 1개의 상자가 최대 공약수가 되는 것이다.
• 이것을 수학적으로 증명하면 다음과 같다.

 

수학적으로 증명하기

• 두 수 `A`와 `B`가 주어졌을 때 (단, `A ≥ B`), 두 수 A와 B의 최대 공약수를 `G`라고 하면 다음과 같이 나타낼 수 있다.

$$A = Ga, \;B = Gb \; (\text{a와 b는 서로소})$$

• `A`를 `B`로 나눈 몫을 `Q`라고 하고 나머지를 `R`이라고 한다면 다음과 같이 나타낼 수 있다.

$$A = BQ + R$$

• 여기서 `B`와 `R`의 최대 공약수가 `G`임을 증명하면 된다.
• `B = Gb` 이고, `R = A - BQ = Ga - GbQ = G(a - bQ)` 가 된다.

$$B = Gb, \; R = G(a - bQ)$$

• 따라서 `B`와 `R`의 공약수는 `G`가 되는데, `b` 와 `a - bQ` 가 서로소임을 증명하면 공약수 `G` 는 최대 공약수가 된다.
• `b` 와 `a -bQ` 가 서로소임은 귀류법을 써서 증명할 수 있다.

만약 `b` 와 `a - bQ` 가 서로소가 아니라고 가정한다면, `b` 와 `a - bQ` 는 공통된 약수를 가지고 있을 것이고, 공통된 약수를 `p` 라고 한다면 $b = np, \; a - bQ = mp$ 라 놓을 수 있다. $a = mp + bQ$ 가 되고 `b = np` 이므로 $a = mp + bQ = mp +npQ = p(m + nQ)$ 가 된다. $a = p(m + nQ)$ 이고 $b = np$ 가 되기 때문에 `a` 와 `b` 는 공약수 `p` 를 가진다. 이것은 `a` 와 `b` 가 서로소라는 가정에 모순이 되므로 `b` 와 `a - bQ` 는 서로소이다.

• `b` 와 `a - bQ` 는 서로소이기 때문에 `B` 와 `R` 의 최대 공약수 `G` 는 `A` 와 `B` 의 최대 공약수가 된다.
• 따라서 `A` 를 `B` 로 나눈 몫을 `Q` 라고 하고, 나머지를 `R` 이라고 한다면 $gcd(A, B)$ 는 $gcd(B, R)$ 과 같다.

int gcd(int x, int y) {
    int r;
    
    while (y) {
        r = x % y;    // (1), (4), (7)
        x = y;        // (2), (5), (8)
        y = r;        // (3), (6), (9)
    }
    return x;
}

• 두 개의 정수`12` 와 `18` 을 `x` 와 `y` 에 전달하고, `x` 를 `y` 로 나눈 나머지를 `r` 이라고 할 때, `x` 와 `y` 의 최대 공약수는 `y` 와 `r` 의 최대 공약수와 같으므로 먼저 `x` 를 `y` 로 나눈 나머지 `r` 을 구한 후, 같은 작업을 반복하기 위해서 `x` 의 값에 `y` 의 값을 대입하고 `y` 의 값에 `r` 의 값을 대입한다.
• `x` 를 `y` 로 나눈 나머지가 `0` 일 때, 제수 `y` 가 최대 공약수가 되지만, 한 번 더 다음 과정을 진행하면 `x = y` 에 의해서 `x` 의 값은 `y` 의 값이 되고, `y = r` 에 의해서 `y` 의 값은 `0` 이 되므로 최대 공약수인 `x` 의 값을 반환한다.

 

코드

#include <iostream>
using namespace std;

int gcd(int x, int y) {
    int r;
    
    while (r) {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main() {
    int a, b;
    
    cin >> a >> b;
    cout << gcd(a, b) << '\n';
    
    return 0;
}

12 18
6

 

최소 공배수(LCM; Least Common Multiple)

• 두 개 이상의 자연수들의 공통인 배수들의 모임을 공배수(Common Multiple)라고 하고, 공배수 중에서 가장 작은 수를 최소 공배수(Least Common Multiple)라고 한다.
• 예) `3` 의 배수는 $\{3, 6, 9, 12, \cdots \}$ 이고 `4` 의 배수는 $\{4, 8, 12, 16, \cdots \}$ 일 때, 두 수 `3` 과 `4` 의 공배수는 $\{ 12, 24, 36, \cdots \}$ 이고 최소 공배수는 $12$ 가 된다.

 

• 두 개의 자연수 `A` 와 `B` 의 최대 공약수를 `G` 라고 하고 최소 공배수를 `L` 이라고 하면 다음과 같은 관계식이 성립한다.

$$A \times B = L \times G$$

• `A` 와 `B`의 최대 공약수가 `G` 이므로 $A = aG, \; B = bG$ (`a, b` 는 서로소)로 나타낼 수 있다.
• 그러면 두 수의 최소 공배수(`L`)는 $abG$ 가 된다.
• 두 수 `A` 와 `B` 를 곱하면 $AB = aGbG$ 가 되고, 최대 공약수(`G`)와 최소 공배수(`L`)를 곱하면 `LG` 는 `abGG` 가 된다.
• 두 수 `A` 와 `B` 의 곱은 최소 공배수인 `L` 과 최대 공약수인 `G` 를 곱한 값과 같기 때문에 최소 공배수는 알고리즘을 따로 작성하여 구하는 것이 아니라, 두 수 `A` 와 `B` 를 곱한 후 최대 공약수 `G` 로 나누면 구할 수 있다.

 

코드

#include <iostream>
using namespace std;

int gcd(int x, int y) {
    int r;
    
    while (r) {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main() {
    int a, b;
    
    cin >> a >> b;
    cout << a * b / gcd(a, b) << '\n';
    
    return 0;
}

3 4
12

 

재귀 함수를 이용하여 최대 공약수/최소 공배수 구하기

• 최대 공약수와 최소 공배수를 다음과 같이 재귀 함수를 이용하여 구할 수 있다.

// GCD : 최대공약수
int gcd(int x, int y) {
	if (x == 0) return y;
	else return gcd(y % x, x);
}

// LCM : 최소공배수
int lcm(int x, int y) {
	return (x * y) / gcd(x, y);
}

 

참고 사이트

• 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

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

• https://namu.wiki/w/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

최소공배수 - 나무위키

• https://namu.wiki/w/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98

최대공약수 - 나무위키