프로그래머스 / 연습문제 / 최대공약수와 최소공배수

https://programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

#include <string>
#include <vector>
 
using namespace std;
 
int gcd(int a, int b)
{
    while (b != 0)
    {
        int remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}
vector<int> solution(int n, int m) {
    vector<int> answer;
    answer.push_back(gcd(n, m));
    answer.push_back(n*m/answer[0]);
    return answer;
}

먼저 유클리드 호제법을 사용하여 최대공약수를 구한다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

n 과 m 사이의 최소공배수는

n * m 값 / 최대공약수이다.