유클리드 호제법

* a와 b의 최대공약수(gcd) / 최대공배수(lcm) 는 gcd*lcm=a*b를 성립한다

• 유클리드 호제법으로 최대공약수를 쉽게 구할 수 있다.

코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    /* 유클리드 호제법 */
    int c,a=n,b=m;
    while(b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    answer.push_back(a);
    // 나오는 a값이 최대공약수이다 (유클리드 호제법)
    answer.push_back(n*m/a);
    return answer;
}