[C++] 백준 2609번 : 최대공약수와 최소공배수 (S5)

#문제

www.acmicpc.net/problem/2609

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

#풀이 & 학습한 내용

최대공약수는 1부터 두 수 중 작은 수(b)까지 for문으로 살피면서 두 수 모두에 나누어 떨어지면 GCD값을 갱신시켜준다.

최소공배수는 두 수 중 작은 수(b)부터 두 수의 곱(b*a)까지 for문으로 살피면서 두 수 모두에 의해 나누어 떨어지면 LCD값을 결정하고 for문을 탈출한다.

 

cf) 최대공약수는 유클리드 호제법을 통해서 구할 수도 있다. GCD(a, b)=GCD(b, a% b)를 이용하고, a% b가 0일 때 그때 b가 최대공약수이다.

    최소공배수는 최대공약수를 통해 (a*b)/gcd로 구할 수 있다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    int a, b;
    int GCD;//최대공약수: greatest common divisor
    int LCM;//최소공배수: largest common multiple
 
    cin >> a >> b;
    if (a > b) swap(a, b);//a<=b로 만들기
 
    for (int i = 1; i <= b; i++) {
        if (a%i == 0 && b%i == 0)
            GCD = i;
    }
 
    for (int i = b; i <= b * a; i++) {
        if (i%a == 0 && i%b == 0) {
            LCM = i;
            break;
        }
    }
    
    cout << GCD << '\n' << LCM << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Math/BOJ_2609.cpp

HoYoungChun/BOJ_algorithm