[ALGORITHM] 12. 최대 공약수와 최소 공배수 구하기

C++ 17부터 제공하는 std::gcd()와 std::lcm을 사용해도 되지만

모든 작업환경이 C++ 17을 만족하지는 않기에 유클리드 호제법을 사용해 직접 구현해 봤다.

 

 

재귀함수

 

int gcd(int a, int b) {

	return (b == 0) ? a : gcd(b, a % b);
}

 

 

반복문

 

int gcd(int a, int b) {

    while (b != 0) {
    
        int temp = b;
        b = a % b;
        a = temp;
    }
    
    return a;
}

 

 

최소 공배수(LCM) 구하기

 

int lcm(int a, int b) {

	return a * b / gcd(a, b);
}