[Algorithm] 최대공약수(GCD), 최소공배수(LCM)

최대 공약수(GCD), 최소 공배수(LCM)

 

1. 알고리즘의 이해

유클리드 호제법을 사용하여 최대공약수를 구한 후, 이를 이용하여 최소공배수를 구한다!!

 

 

2. 유클리드 호제법

두개의 정수 사이에 존재하는 최대공약수(GCD)를 구하는 알고리즘

 

1. 정수 a, b 에서 더 큰 값을 a에 위치시킨다
2. a를 b로 나눈 나머지를 r 이라고 한다
3. a는 b의 값으로, b는 r의 값으로 갱신시켜준다
4. b가 0이 됐을 때의 a값이 GCD 값이다

 

 

3. 소스 코드

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

int gcd(int a,int b){
    // a에 항상 큰 값을 위치시켜야함
    int tmp;
    if(a < b){
        tmp = a;
        a = b;
        b = tmp;
    }
    
    // 유클리드 호제법
    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(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n1,n2;
    
    cin >> n1 >> n2;
    
    cout << gcd(n1,n2) << "\n";
    cout << lcm(n1,n2) << "\n";
    
    return 0;
}