GCD(Greatest Common Divisor) 알고리즘 GCD란 영어 단어 그대로 최대공약수라는 뜻이다. 최대공약수는 공약수 중에서 가장 큰 값을 의미한다. 우선 최대공약수를 구하기 위해서는 공약수가 무엇인지부터 알아내는 것이 먼저이다. 최대공약수를 구하기 전에 공약수를 알아보자! 공약수 사전에서는 둘 이상의 정수에 공통된 약수라고 정의되어 있다. 정수 두 개를 놓고 보았을 때, 둘 다 나누어 떨어지게 만들 수 있는 수를 공약수라고 한다. 예를 들어 16과 24가 있다고 했을 때, 16의 약수: 1, 2, 4, 8, 16 24의 약수: 1, 2, 3, 4, 6, 8, 12, 24 16과 24의 공약수는 1, 2, 4, 8이다. 그렇다면 최대공약수는 8이 되는 것이다. 유클리드 호제법(Euclidea..
