유클리드 호제법 유클리드 호제법은 유클리드가 발견한 두 수의 최대공약수를 구하는 방법이다. 원래 우리가 초등학교때 배운 방법은 컴퓨터에서 실행하려고 할 때, 두 수가 커지면 비효율적으로 동작하게 된다. 따라서 유클리드 호제법을 이용해 최대공약수를 구하고 그 다음 최소공배수를 구해야한다. 최대공약수 반복문을 이용해 구현한 유클리드 호제법은 다음과 같다. int GCD(int a, int b) { while(b!=0) { int c = a % b; a = b; b = c; } return a; } 최소공배수 두 수의 곱은 두 수의 최대공약수와 최소공배수와 같다는 수학적 성질을 이용해 최소공배수를 구한다. 예를 들어 10와 15의 최대공약수는 5이다. 따라서 최소공배수를 구하기 위해서 다음과 같은 식을 만족한..
