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

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야합니다.

제한사항

• 두 수는 1 이상 1000000이하의 자연수입니다

문제 링크

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

프로그래머스

 

풀이[c++]

#include <vector>

using namespace std;

int greatest_common_divisor(int num1, int num2){
    if(!(num1%num2))
        return num2;
    return greatest_common_divisor(num2,num1%num2);
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    int gcd = greatest_common_divisor(n,m);
    int lcm = n*m/gcd;
    answer.push_back(gcd);
    answer.push_back(lcm);
    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

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