유클리드 호제법(Greatest Common Divisor : 최대공약수)

최대공약수의 정의 ===> 최대공약수란 주어지는 두 정수의 약수 중에서 가장 큰 공통되는 약수를 뜻한다. 예를들어 280과 30의 약수는 280의 약수 : 1, 2, 4, 5, 7, 8, 10, 14, 20, 28, 40, 56, 70, 140, 280 30의 약수 : 1, 2, 3, 5, 6, 10, 15, 30 이다. 이중 공통되는 약수는 1, 2, 5, 10이며 그중에 10이 최대공약수(GCD)이다. 수학교과서에 나오는 최대공약수를 구하는 방법은 소인수분해를 이용하여 구한다. 허나 소인수분해를 이용한 최대공약수를 구하는 방법은 손으로 풀기에는 더할나위 없이 좋지만 컴퓨터로 구현하기에는 조금은 껄끄럽다. 그래서 유클리드의 알고리즘을 컴퓨터에서 쓴다. 유클리드 알고리즘 유클리드 알고리즘은 뺄셈과 두 값..
study/Java 2007. 10. 4. 00:00
1