유클리드 호제법 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