유클리드 호제법 - 최대 공약수를 구할 때 사용한다.N의 약수 찾기1 ~ N까지 나누어서 나머지가 0이 되는 수의 개수 찾기 = 복잡도 N호제법 - 서로 나눈다!두 자연주 a,b에 대해 (a>b) a를 b로 나눈 나머지를 r이라 하면 a,b의 최대 공약수는 b와 r의 최대 공약수와 동일하다.b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수이다.1071과 1029를 구하자!1071 % 1029 = 421029 % 42 = 21 42는 21로 나누어 떨어지므로 최대 공약수는 21이다! 코드로 구현하자! def GCD(a,b): while b: a,b = b,a%b return aGCD - 최..