[자바] 유클리드 알고리즘(최대공약수 찾기)
유클리드 알고리즘(최대공약수 찾기) 최대 공약수란 최대공약수(GCD : Greatest Common divisor)는 고대 그리스의 수학자인 유클리드에 의해서 발견되었다. 최대 공약수란 주어진 두정수의 약수 중에서 가장큰 공통이 되는 약수를 말한다. 50 : 1, 2, 5, 10, 25, 50 20 : 1, 2, 4, 5, 10, 20 이두 정수의 공통되는 것은 1,2,4,10 이며 가장큰것 10이 최대 공약수가 되는것이다. 기본적으로 중학교때 배운 과정에서는 소인수분해를 하여서 최대공약수, 최대 공배수를 구할수 있다. 기본적인 이해는 끝이 났으니 유클리드의 알고리즘에 대해 알아보자. 유클리드의 알고리즘은 최대공약수의 성질을 이용하여 뺄셈과 두 값의 교환이라는 기본적인 동작으로만 최대 공약수를 구할 수 ..
더보기