[프로그래머스/c++] 최대공약수와 최소공배수(유클리드 호제법)

유클리드 호제법

 

a, b의 수가 있을 때

a, b의 최대공약수 gcd(a, b)는 gcd(b, a%b)로 표현 가능하다.

 

Ex) 12와 8의 최대공약수 구하기

gcd(12, 8) = gcd(8, 12%8) = gcd(8, 4) = gcd(4, 8%4) = gcd(4,0) = 4

 

최대공약수와 최소공배수의 곱은 두 수의 곱과 같으므로

lcm(a, b) * gcd(a, b) = a*b

따라서 a, b의 최소공배수 lmc(a, b)=(a*b)/gcd(a, b)가 된다.

 

---

최대공약수와 최소공배수를 구하는 함수 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    int a=n, b=m, r;
    while(b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    answer.push_back(a); // 최대공약수
    answer.push_back((n*m)/a); // 최소공배수
    
    return answer;
}