최대공약수 계산기 - 수의 최대공약수

최대공약수(GCF)는 최대공약수(GCD) 또는 최대공약수(HCF)라고도 하며, 주어진 정수 집합의 각 수를 나머지 없이 나눌 수 있는 가장 큰 양의 정수입니다. 예를 들어 12와 18의 최대공약수는 6입니다. 6이 12와 18을 모두 정확히 나눌 수 있는 가장 큰 수이기 때문입니다. 최대공약수를 구하는 대표적인 알고리즘은 유클리드 알고리즘과 소인수분해입니다. 큰 수에서는 유클리드 알고리즘이 더 효율적입니다. 이 방법은 수의 쌍 (a, b)를 (b, a mod b)로 반복해서 바꾸다가 나머지가 0이 될 때까지 진행하며, 마지막으로 0이 아닌 b가 최대공약수입니다. 이 알고리즘은 O(log min(a,b)) 단계로 동작하므로 매우 큰 정수에도 빠릅니다. 소인수분해는 각 수를 소수 거듭제곱의 곱으로 나타낸 뒤, 모든 수에 공통으로 나타나는 각 소수의 최소 지수를 곱해 최대공약수를 구합니다. 예를 들어 12 = 2^2 * 3, 18 = 2 * 3^2 이므로 GCF(12, 18) = 2^1 * 3^1 = 6입니다. 큰 수에서는 유클리드 알고리즘보다 비효율적이지만, 왜 그 값이 되는지 이해하기에는 매우 좋습니다. 최대공약수는 실생활에서도 많이 쓰입니다. 산술에서는 분수를 기약분수로 줄일 때 사용합니다. a/b를 약분하려면 분자와 분모를 GCF(a, b)로 나누면 됩니다. 기하에서는 두 길이의 최대공약수가 나머지 없이 둘 다 잴 수 있는 가장 긴 눈금을 뜻합니다. 컴퓨터 과학에서는 모듈러 연산, RSA 키 생성 같은 암호 알고리즘, 데이터 압축 등에 등장합니다. 두 개를 넘는 수의 최대공약수는 반복적으로 계산합니다. GCF(a, b, c) = GCF(GCF(a, b), c) 입니다. 이 계산기는 양의 정수를 몇 개든 처리할 수 있으며, 유클리드 알고리즘(빠른 결과)과 소인수분해(자세한 단계 표시)를 모두 지원합니다. 소인수분해 보기는 인수와 나눗셈을 배우는 학생에게 특히 유용합니다.