BOJ 2609 · 최대공약수와 최소공배수

알고리즘 분류 : 수학  

최대공약수(GCD; greatest common divisor)는 유클리드 호제법(Euclidean algorithm)을 이용하여 구현할 수 있다.

• r은 x를 y로 나눈 나머지 (r = x%y) 
• GCD(x, y) = GCD(y, r) 를 r이 0이 될 때까지 반복적으로 수행
• r이 0일 때, y는 최대공약수이다.

최소공배수(LCM; least common multiple)는 미리 구한 최대공약수를 이용하여 구현할 수 있다.

• g = GCD(x, y)
• LCM = (x*y)/g

---

C++ 소스코드

#include <iostream>
using namespace std;

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

int lcm(int x, int y) {
    return (x*y)/gcd(x,y);
}

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

✓ gcd 함수는 재귀함수로 구현할 수 있다.

int gcd(int x, int y) {
    if (y == 0) return x;
    else return gcd(y, x%y);
}

---

Python 3 소스코드

def gcd(x, y):
    while y is not 0:
        r = x%y
        x = y
        y = r
    return x

def lcm(x, y):
    return (x*y)//gcd(x,y)

a, b = map(int, input().split())
print(gcd(a,b))
print(lcm(a,b))

---

참고

• 백준 온라인 저지 : BOJ 2609
• 위키피디아 : 유클리드 호제법
• 위키피디아 : 최대공약수
• 위키피디아 : 최소공배수