이 계산기는 무엇을 하나요?
두 개 이상의 양의 정수를 입력하면 세 가지 결과를 한꺼번에 보여 줍니다. 각 수의 약수(나누어떨어지게 하는 수) 전체 목록, 모든 수가 공통으로 가지는 공약수, 그리고 최대공약수(GCF, 영어로는 GCD라고도 함)입니다. 분수를 약분하거나 식을 인수분해할 때, 또는 정수론 숙제를 풀 때 유용합니다.
사용 방법
자연수를 쉼표로 구분해 입력하세요. 예를 들어 136, 64, 24, 16처럼 적으면 됩니다. 그러면 각 수의 약수 목록이 오름차순으로 표시되고, 이어서 공약수와 최대공약수(GCF) 값이 나타납니다. 입력값은 반드시 양의 정수여야 하며, 0이나 음수, 소수는 약수를 구하는 데 사용할 수 없습니다.
계산 원리
정수 d가 n의 약수라는 것은 \(n \bmod d = 0\), 즉 나머지 없이 나누어떨어진다는 뜻입니다. 모든 약수를 빠르게 찾으려면 i를 1부터 n의 제곱근까지 차례로 확인합니다. i가 n을 나누어떨어지게 하면 \(i\)와 \(n/i\) 둘 다 약수가 됩니다. 여러 수의 최대공약수는 유클리드 호제법을 두 수씩 적용해 구합니다. b가 0이 아닌 동안 (a, b)를 (b, a mod b)로 계속 바꿔 가다가, 마지막에 남는 a가 바로 최대공약수입니다. $$\gcd(a, 0) = a, \quad \gcd(a, b) = \gcd(b, \; a \bmod b)$$ 한 가지 알아 두면 좋은 사실은, 전체 수들의 공약수는 곧 최대공약수의 약수와 정확히 같다는 점입니다. $$\text{CommonFactors} = \{\, d : g \bmod d = 0 \,\}, \quad g = \gcd(n_1, n_2, \dots)$$
예제 풀이
136, 64, 24, 16의 경우를 봅시다. 16의 약수는 1, 2, 4, 8, 16이고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24, 64의 약수는 1, 2, 4, 8, 16, 32, 64, 136의 약수는 1, 2, 4, 8, 17, 34, 68, 136입니다. 유클리드 호제법을 적용하면 \(\gcd(16, 24) = 8\), 다시 \(\gcd(8, 64) = 8\), \(\gcd(8, 136) = 8\)이 되어 최대공약수는 8입니다. 8의 약수는 1, 2, 4, 8이며, 바로 이 값들이 공약수가 됩니다.
자주 묻는 질문
GCF와 GCD는 같은 건가요? 네, 같습니다. 영어의 "greatest common factor(최대공약수)"와 "greatest common divisor"는 같은 값을 가리키는 두 가지 이름일 뿐입니다.
공통 약수가 하나도 없으면 어떻게 되나요? 모든 양의 정수는 1을 공통 약수로 가지므로, 공약수는 최소한 {1}이고 최대공약수도 최소 1입니다. 공통 약수가 1뿐인 수들을 서로소(coprime)라고 합니다.
숫자를 하나만 입력해도 되나요? 네. 그 수의 약수가 나열되고, 최대공약수는 그 수 자신이 됩니다.
