[프로그래머스][C++][LV 1] 최대공약수와 최소공배수

 

유클리드 호제법을 통해 최대공약수를 구할 수 있다 

유클리드 호제법

2개의 자연수에 대해서. a 를 b로 나눈 나머지를 r 이라고 한다면. ( 단, a > b )

a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라 b를 r로 나눈 나머지를 구하는 과정을 반복하여.

나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대 공약수다.

#include <string>
#include <vector>

using namespace std;

int gcd(int a,int b)            //유클리드 호제법
{
    if(b==0) return a;
    else return gcd(b,a%b);     
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    int gcd_num = gcd(max(n,m),min(n,m));
    
    answer.push_back(gcd_num);
    answer.push_back((n*m)/gcd_num);                //최소공배수 = 기존 두 수의 곱 / 최대공약수
    return answer;
}