[C++] 최대공약수 최소공배수

최대공약수 - 유클리드 호제법

int gcd(int a, int b){
    int k;
    while(m!=0){
        k = a % b;
        a = b;
        b = k;
    }
    return a;
}

유클리드 호제법은 최대공약수를 찾는 가장 빠른 방법이라더라.

 

덧붙여서 gcd는 헤더파일 numeric에 이미 있다.(!)

#include <numeric>

c = std::gcd(a,b);

 

최소공배수

int lcm(int a, int b){
	return a * b / gcd(a, b);
}

a * b = gcd(a, b) * lcm(a, b)를 이용한다.