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

 유클리드 호제법

2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

시간복잡도: O(logN)

 

 

<< 최대공약수 구하는 코드 >>

int gcd(int num1, int num2) {
	if (num2 == 0) return num1;
    else return gcd(num2, num1 % num2);
}

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

 

 

<< 최소공배수 구하는 코드 >>

cout << num1 * num2 / gcd(num1, num2);