-
유클리드 호제법(Euclidean algorithm)알고리즘 2024. 6. 9. 14:53
유클리드 호제법은 두 정수의 최대공약수(Greatest common divisor: GCD)를 구하는 효율적이고 간단한 알고리즘입니다. 기원전 300년경 그리스 수학자 유클리드(Euclid)가 편찬한 유클리드 원론(기하학 원론)에서 처음 소개돼었습니다. 가장 오래된 알고리즘으로 알려져 있습니다.
두 정수 와 가 주어졌고 는 보다 크다고 하겠습니다. . 를 로 나누면 이고 이는 이렇게 다시 쓸 수 있습니다. 여기서 는 몫(quotient)이고 은 나머지(remainder)입니다. 여기서 와 의 최대공약수를 라고 표현하면 아래식이 성립합니다. 와 의 최대공약수는 와 의 최대공약수와 같습니다. 여기서 다시 를 로 나눈 나머지 을 구하고 다시 을 로 나누는 과정 반복하다가 나머지가 0이 되었을 때 나누는 수가 최대공약수가 됩니다. 몇가지 예를 들어보겠습니다.두 수 4098, 2024의 최대공약수는 2입니다.
두 수 123456, 9999의 최대공약수는 2입니다.
정리하자면 다음과 같습니다.1. 두 정수 중 큰 수를 작은 수로 나눈 나머지로 바꿉니다. (만약
라면 )
2. 두 정수 중 한쪽이 0이 될 때까지 반복합니다. 이때 0이 아닌 쪽이 최대공약수입니다.이에 대한 증명은 이 글에서 다루지 않습니다.
다음은 위 내용을 C언어로 구현한 코드입니다. 유클리드 호제법의 시간 복잡도는
입니다.int gcd(int a, int b) { while (a >= 1 && b >= 1) { if (a >= b) a = a % b; else b = b % a; } if (a > 1) return a; return b; } int recur_gcd(int a, int b) { if (b == 0) return a; else return recur_gcd(b, a % b); }
'알고리즘' 카테고리의 다른 글
검사 범위 최소화하여 약수 구하기 (2) 2024.06.08