유클리드의 알고리즘 ( 최대 공약수 찾기 )
최대공약수 (GCD : Greatest Common divisor)를 구하는 방법은 약 2천년 전의 고대 그리이스 수학자인 유클리드에 의해 발견 되었다. 최대 공약수는 주어지는 두 정수의 약수 중에서 가장 큰 공통되는 약수를 말한다. 예를 들어 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 280의 약수와 30의 약수 중 공통되는 것은 1, 2, 5,10 이며 이 중에서 제일 큰것은 10이며 이것이 바로 최대공약수이다. 수학 교과서 에서 최대 공약수를 구할 떄에는 소인수 분해를 이용하여 구한다. 다음과 같이 280과 30을 소인수..
2009. 2. 24.