최대공약수/ 최소공배수_ 백준 2609번/1934번

지금은 코드플러스에서 기초 알고리즘 강의를 구매해서, 관련 문제를 푸는 중인데

백준 2609번이랑 1934번이 비슷한 문제인거 같아서 한번에 정리해보려고 한다.

---

 

먼저, 최대공약수의 경우에는 

유클리드 호제법을 이용하는 방법을 사용하는 것이 좋다. 

 

여기서 유클리드 호제법이란, a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a,b) = GCD(b,r)인 것을 활용하여, r의 값이 0이 되면 그때의 b의 값이 최대 공약수라는 것을 활용한다.

 

최소공배수의 경우에는 위에서 구한 최대공약수를 활용하여 구할 수 있다.

최소공배수는 두수의 공통된 배수 중 가장 작은 정수이기 때문에, 두수 a, b의 최대공약수가 g라고했을 때 

최소공배수 = g * (a/g) * (b/g)가 된다.

 

---

2609번

#include <iostream>
#include <cstdio>
using namespace std;

int gcd(int a, int b) // 최대공약수 _ 유클리드 호제법 활용
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
} 

int main(void)
{
    int a, b;
    int Gcd, Lcm;
    scanf("%d %d", &a, &b);
    Gcd = gcd(a, b);
    Lcm = Gcd * (a / Gcd) * (b / Gcd);
    printf("%d\n%d", Gcd, Lcm);
}

1934번

#include <iostream>
#include <cstdio>
using namespace std;

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main(void)
{
    int a, b;
    int Gcd, Lcm;
    int count;
    scanf("%d", &count);
    while (count--)
    {
        scanf("%d %d", &a, &b);
        Gcd = gcd(a, b);
        Lcm = Gcd * (a / Gcd) * (b / Gcd);
        printf("%d\n", Lcm);
    }
}