유클리드 호제법

유클리드 호제법: 최대공약수(greatest common divisor)를 먼저 구한 뒤, 공식을 통해 최소공배수(least common multiple)를 구하는 방법

$lcm=a\ast b/gcd$

int GCD(int m, int n) {
    // 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수이다.
    while (n!=0) {
        int r = m % n;
        m = n;
        n = r;
    }
    
    return m;
    // 주의: while 문의 조건에 b를 넣고, a를 리턴한다.
}