🔢 최대공약수/최소공배수 계산기
두 수의 최대공약수(GCF)와 최소공배수(LCM)를 계산합니다.
A, B 값을 입력하면 소인수 비교가 표시됩니다
최대공약수 (GCF/GCD)
두 수 또는 여러 수의 공통된 약수 중 가장 큰 수입니다. 소인수분해 후 공통 소인수의 최솟값 지수 곱으로 구합니다.
GCF(12, 18) = GCF(2²×3, 2×3²) = 2¹×3¹ = 6
최소공배수 (LCM)
두 수 또는 여러 수의 공통된 배수 중 가장 작은 수입니다. 소인수분해 후 모든 소인수의 최댓값 지수 곱으로 구합니다.
LCM(12, 18) = 2²×3² = 36
유클리드 호제법
두 수의 최대공약수를 구하는 효율적인 알고리즘입니다. 나머지가 0이 될 때까지 반복합니다.
GCF(a, b) = GCF(b, a mod b)
GCF(48, 18) → GCF(18,12) → GCF(12,6) → GCF(6,0) = 6
GCF ↔ LCM 관계
GCF(a,b) × LCM(a,b) = a × b
LCM(a,b) = a × b ÷ GCF(a,b)
활용
분수의 약분(GCF 이용), 통분(LCM 이용), 주기 문제, 타일 배치 최적화 등에 활용됩니다.