최대공약수, 최소공배수 알고리즘

최대공약수 GCD : Greatest Common Divisor

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

 

 

 

최소공배수 LCM : Least Common Multiple

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

 

 

그외에

#include <numeric> 라이브러리 내의 함수인 std::gcd 나 std::lcm을 써도 됨