최대 공약수와 최소 공배수 구하기(유클리드 호제법)

Intro

이 글은 최대 공약수와 최소 공배수를 구하는데 사용되는 유클리드 호제법에 대한 정보를 담은 글입니다.

---

최대 공약수 구하기 알고리즘(유클리드 호제법)

최대 공약수의 정의: 두 수가 서로 공통으로 가지고 있는 약수 중에 가장 큰 수

유클리드 호제법이란?

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

알고리즘의 프로세스는 다음과 같다.

[출처: Inch Calculator]

두 수 A와 B(A>B)의 최대 공약수를 구한다면, 큰 수 A에 작은 수 B를 나눈 나머지를 구한다.

그리고 이 나머지를 작은 수 B에 나눈다.

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

나머지가 0이 되면 작은 수를 반환한다.

이 수가 최대 공약수이다.

---

그럼 최소 공배수는?

최소 공배수도 간접적으로(?) 유클리드 호제법을 통해 구할 수 있다.

최소 공배수의 정의: 두 수에 서로 공통으로 존재하는 배수 중 가장 작은 수

최소 공배수 구하기 방법

두 수 A와 B를 서로 곱한 후 최대 공약수로 나누면 된다.

---

백준 2609번

최소 공배수와 최대 공약수를 구하는 대표적인 문제로 백준 2609번 문제를 뽑을 수 있다.

풀이 코드

#include <stdio.h>

int GCB(int a, int b){ // 최대 공약수
    
    int A = 0;
    int B = 0;
    if (a > b){ // 큰 수에 작은 수 나눠서 하기 때문
        A = a;
        B = b;
    }
    else {
        A = b;
        B = a;
    }
    
    if(A % B == 0){
        return B;
    }
    else{
        GCB(B, A%B);
    }
    
}

int LCM(int a, int b, int r){ // 최소 공배수
    return (a*b)/r;
}

int main(){
    
    int A;
    int B;
    
    scanf("%d %d", &A, &B);
    
    int n = GCB(A, B);
    
    printf("%d\n", n);
    
    printf("%d", LCM(A, B, n));
    
}