최대공약수 계산기

최대공약수 (GCD) 계산기

두 개 이상의 양의 정수를 쉼표로 구분하여 입력하면 최대공약수를 계산합니다.

숫자 입력:

값을 입력하고 '계산하기' 버튼을 눌러주세요.

계산 후 풀이 과정이 여기에 표시됩니다.

최대공약수(Greatest Common Divisor, GCD)는 둘 이상의 정수의 공통된 약수 중에서 가장 큰 수를 의미합니다. 중학교 수학에서 분수의 약분, 최소공배수(LCM) 계산 등에 필수적으로 활용되는 개념입니다.

공약수: 두 개 이상의 정수의 공통된 약수입니다. 예를 들어, 12의 약수는 1, 2, 3, 4, 6, 12이고, 18의 약수는 1, 2, 3, 6, 9, 18입니다. 이들의 공약수는 1, 2, 3, 6입니다.
최대공약수 (GCD): 공약수 중에서 가장 큰 수입니다. 위 예시에서 12와 18의 최대공약수는 6입니다.

최대공약수를 찾는 방법은 여러 가지가 있지만, 컴퓨터 프로그래밍에서 효율적으로 사용되는 방법은 '유클리드 호제법'입니다.

유클리드 호제법 (Euclidean Algorithm):
두 개의 양의 정수 a, b (a > b)가 있을 때, a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 이 과정을 나머지가 0이 될 때까지 반복하며, 나머지가 0이 되었을 때 나누는 수(b)가 두 수의 최대공약수가 됩니다.

수식: gcd(a, b) = gcd(b, a % b) (단, a % b는 a를 b로 나눈 나머지)

예시 (12와 18의 최대공약수):
- 1단계: 18을 12로 나눕니다. 18 = 1 × 12 + 6 (나머지 6)
- 2단계: 12를 나머지 6으로 나눕니다. 12 = 2 × 6 + 0 (나머지 0)
- 나머지가 0이 되었으므로, 마지막에 나눈 수인 6이 12와 18의 최대공약수입니다.
세 개 이상의 수의 GCD: 여러 수의 최대공약수는 처음 두 수의 최대공약수를 구한 후, 그 결과와 다음 수의 최대공약수를 구하는 방식으로 반복하여 계산할 수 있습니다. 예를 들어, gcd(a, b, c) = gcd(gcd(a, b), c)와 같습니다.

이 최대공약수 계산기를 통해 수학 문제 해결 능력을 향상시키고, 더 복잡한 수론 문제에도 자신감을 가지세요!