# 12940 최대공약수와 최소공배수

문제 정리

두 수의 [최대공약수, 최소공배수] 배열 반환하기

생각해보기

gcd 이런 함수 써도 되는건가?… 아니면 내가 직접 구해야 하는지?!ㅠㅠ 우선 직접 하는 쪽으로 해보자…

코드 쓰기

2개의 수의 최대공약수 - 유클리드 호제법, 최소공배수 - 최대공약수를 통해 구하면 됨!
유클리드 호제법

두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 “r이 0이면 그때 b가 최대공약수이다.”라는 원리를 활용한 알고리즘

재귀로 풀기

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

반복문으로 풀기

int GCD(int a,int b){
    while(1){
        int r = a%b;
        if(r==0) return b;
		
        a = b;
        b = r;
    }
}

최소공배수

int lcm(int a, int b){
    return a * b / gcd(a,b);
}

라고 한다…

내 풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    int a = 0; int b = 0;
    
    // a>b 만들어주기
    if(n<m){
        a = m;
        b = n;
    } else {
        a = n;
        b = m;
    }
    
    while(1){
        int r = a%b;
        if (r==0) { break; };
        a = b;
        b = r;
    }
    
    answer.push_back(b);
    
    // 최소공배수 구하기
    answer.push_back(n*m / b);
    
    return answer;
}

풀고 나서 알게된 것

최소공배수 최대공약수 구하는 법 알아두기…^^ 하