백준 2609 - 최대공약수와 최소공배수

문제

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

풀이

유클리드 호제법을 사용하면 최대 공약수를 쉽게 구할 수 있다.

gcd(a, b) 를 a와 b의 최대 공약수라고 하고 a % b = r 이라고 할 때,

gcd(a, b) = gcd(b, r) 이다. r이 0 일때 b가 최대 공약수다.

 

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

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

 

최소 공배수는 최대 공약수를 이용하면 쉽게 구할 수 있다.

 

 

코드

#include <iostream>
 
using namespace std;
 
int A, B;
 
int gcd(int A, int B)
{
    while (B != 0)
    {
        int r = A % B;
        A = B;
        B = r;
    }
    return A;
}
 
int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> A >> B;
    cout << gcd(A, B) << '\n' << lcm(A, B);
 
    return 0;
}