BOJ 1934 · 최소공배수

알고리즘 분류 : 수학  

최소공배수는 유클리드 호제법을 이용하여 구현할 수 있다. 자세한 내용은 이곳을 참조.

---

C++ 소스코드

#include <cstdio>

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

int main() {
    int t, a, b;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &a, &b);
        printf("%d\n", (a*b)/gcd(a,b));
    }
    return 0;
}

---

Python 3 소스코드

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

for _ in range(int(input())):
    a, b = map(int, input().split())
    print((a*b)//gcd(a,b))

---

참고

• 백준 온라인 저지 : BOJ 1934