최대공약수·최소공배수
GCD·LCM을 즉시 산출
최대공약수·최소공배수 계산기란?
최대공약수(GCD)는 두 개 이상의 정수를 동시에 나누어 떨어지게 하는 가장 큰 수이고, 최소공배수(LCM)는 그 정수들의 공통 배수 중 가장 작은 수입니다. 이 계산기는 콤마로 구분한 정수 여러 개를 받아 GCD와 LCM을 즉시 계산합니다.
사용 방법
계산할 양의 정수를 콤마(,)로 구분해 2개 이상 입력한 뒤 계산하기를 누릅니다. 예: 12, 18, 24. 소수·음수·0은 입력할 수 없습니다.
공식·계산 과정
유클리드 호제법: GCD(a, b) = GCD(b, a mod b), b가 0이 될 때까지 반복. LCM(a, b) = (a × b) ÷ GCD(a, b). 숫자가 3개 이상이면 두 개씩 순서대로 누적 계산합니다.
| 입력 | GCD | LCM |
|---|---|---|
| 12, 18 | 6 | 36 |
| 12, 18, 24 | 6 | 72 |
타일 깔기(GCD)와 버스 배차 만남(LCM)으로 보는 실생활 계산
가로 360cm, 세로 240cm인 방을 자투리 조각 없이 정사각형 타일로 완전히 채우고 싶다면, 쓸 수 있는 가장 큰 정사각형 타일의 한 변은 두 길이의 최대공약수와 같아야 합니다. GCD(360, 240)=120이므로 한 변 120cm 타일을 쓰면 가로에 360÷120=3장, 세로에 240÷120=2장, 총 6장으로 빈틈없이 시공됩니다. 만약 임의로 100cm 타일을 골랐다면 360과 240 모두 100으로 나누어떨어지지 않아 가장자리에 자투리가 생깁니다.
버스 배차에서는 반대로 LCM이 쓰입니다. 12분 간격으로 오는 A노선 버스와 18분 간격으로 오는 B노선 버스가 오전 9시에 동시에 출발했다면, 두 버스가 다시 동시에 출발하는 시각은 두 배차 간격의 최소공배수만큼 지난 뒤입니다. LCM(12, 18)=36이므로 36분 뒤인 9시 36분에 두 버스가 다시 함께 출발합니다. 타일은 '더 이상 못 쪼개는 공통 단위(GCD)'를, 배차는 '다시 만나는 공통 주기(LCM)'를 구한다는 점에서 같은 두 정수 문제의 정반대 쓰임입니다.
유클리드 호제법, 한 줄로 이해하기
유클리드 호제법은 큰 수를 작은 수로 나눈 나머지로 계속 바꿔가며 나머지가 0이 될 때까지 반복하는 방법입니다. GCD(48, 18)을 예로 들면: 48 mod 18 = 12 → (18, 12)로 교체, 18 mod 12 = 6 → (12, 6)으로 교체, 12 mod 6 = 0이 되는 순간 직전의 나머지 6이 최대공약수입니다. 이 계산기도 내부적으로 같은 방식을 사용해 아무리 큰 수라도 몇 단계 만에 GCD를 찾아냅니다.