최대공약수를 구할 때 유클리드 호제법을 사용하면 최대 공약수를 쉽게 구할 수 있다. 유클리드 호제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 최대공약수 함수(python) def GCD(a,b): if a < b: (a ,b) = (b, a) while b != 0: (a , b) = (b , a % b) return a 예시 1071과 1029의 최대공약수를 구하면, 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를..