유클리드 호제법 또는 유클리드 알고리즘이라고 불리는 최대공약수를 구하는 방법이 있다.
두 양의 정수 A, B (A > B)의 최대 공약수를 GCD(A,B)라고 하고
R = A mod B라고 할때
(A mod B는 A를 B로 나누었을 때의 나머지이다. 자세한 건 클릭)
GCD(A,B) = GCD(B,R)
이 것이 유클리드 호제법이다.
즉 A와 B의 최대공약수는 B와 A를B로 나누었을때의 나머지의 최대공약수와 같다.
나머지가 0이 될때까지 반복하면 최대 공약수를 구할 수 있다.
예를들어 36과 16의 최대공약수를 구하라!
GCD(36, 16)을 구하는 문제이다.
즉 GCD(36, 16) = GCD(16, 4)
16 / 4 = 0답은 4이다.
이렇게 보면 암산으로도 구하는데 더 복잡한거 아닌가? 라고 생각 할 수 있지만
6080, 3876 의 최대공약수를 구하라!
GCD(6080, 3876) = GCD(3876, 2204) = GCD(2204, 1672) = GCD(1672, 532) = GCD(532, 76)
532 / 76은 0이므로 답은 76이다.
큰 숫자의 최대공약수도 나누기 몇번으로 금방 구할 수 있다.
소스코드
반복문
1 2 3 4 5 6 7 8 9 10 | int EuclideanAlgorithm(int a, int b) { while (b) { int temp = b; b = a%b; a = temp; } return a; } | cs |
재귀
1 2 3 4 5 6 7 | int EuclideanAlgorithm(int a, int b) { if (b == 0) return a; else return EuclideanAlgorithm(b, a%b); } | cs |
증명
GCD(A,B) = d라고 하면 A = dα, B = dβ라고 할 수 있고 GCD(α, β) = 1이다.
(A, B를 최대공약수로 나눈 α, β는 1이외의 공약수가 없기때문에 최대공약수는 1이다.)
그리고 A를 B에 관한식인 A = qB + R로 표현 할 수 있다.
GCD(B, R)은 B = dβ, R = A - qB = d(α - qβ)
즉 GCD(A,B) = GCD(dβ, d(α - qβ))를 보이려면
dβ, d(α - qβ) 두 수에서 d가 공약수이므로
GCD(β, α - qβ) = 1 (즉 서로소)임을 보이면 된다.
GCD(β, α - qβ) = m이라고 하면
β = mx, α - qβ = my로 나타낼 수 있다.
α = my + qβ = my + qmx = m(y+qx) 이므로 GCD(α, β) = m
GCD(α, β) = 1이므로 m은 1이다.
즉 GCD(β, α - qβ) = 1이다. (즉 서로소)
∴ GCD(A, B) = GCD(B, R)