유클리드 호제법은 2개의 자연수 또는 정수의 최대 공약수를 구하는 알고리즘의 하나 입니다.정보올림피아드에서 2개의 최대 공약수를 구하는 문제가 종종 나오는데...이때 유클리드 호제법을 이용해서 문제를 풀어 나가면 훨씬 빠르고 유용하게 사용할 수 있습니다.예를 들면 131 과 109 의 최대 공약수를 구하는 문제같은 경우 131이 3의 배수인지 아닌지 판단 하고 109가 3의 배수인지 아닌지 판단 하는 것보다는 다음과 같이 구하면 훨씬 수월하게 풀릴것 같네요.131 % 109 = 22 이므로22 와 109 의 최대공약수와 동일 하고...109 % 22 = 21 따라서 22와 21의 최대 공약수와 동일 하기 때문에 최대공약수는 1이 나오게 됩니다.131이 소수인지 아닌지 판단 하는 것보다 이렇게 판단하는 것..
