🔢 최대공약수·최소공배수 계산기
숫자를 쉼표나 띄어쓰기로 나눠 넣으세요. 2개부터 20개까지 한 번에 계산하고 풀이 과정도 보여 드려요.
사용법
- 자연수를 쉼표(,)나 띄어쓰기로 나눠 넣어요. 2개부터 20개까지, 15자리 수까지 계산해요.
- 최대공약수와 최소공배수, 각 수의 소인수분해, 공약수 목록이 바로 나와요.
- 아래 풀이에서 소인수분해 방법, 학교에서 배우는 공통 나눗셈(사다리), 두 수일 때 유클리드 호제법 과정을 확인하세요.
기본 개념
| 용어 | 뜻 | 12와 18의 예 |
|---|---|---|
| 약수 | 어떤 수를 나누어떨어지게 하는 수 | 12: 1, 2, 3, 4, 6, 12 |
| 공약수 | 여러 수에 공통인 약수 | 1, 2, 3, 6 |
| 최대공약수 (GCD) | 공약수 중 가장 큰 수 | 6 |
| 공배수 | 여러 수에 공통인 배수 | 36, 72, 108, … |
| 최소공배수 (LCM) | 공배수 중 가장 작은 수 | 36 |
| 서로소 | 최대공약수가 1인 수들 | 8과 15 |
계산 방법 3가지
① 소인수분해
각 수를 소수의 곱으로 나타내요. 12 = 2² × 3, 18 = 2 × 3²이면 공통 소인수 2와 3을 작은 지수로 곱한 2 × 3 = 6이 최대공약수, 나온 소인수를 모두 큰 지수로 곱한 2² × 3² = 36이 최소공배수예요.
② 공통 나눗셈(사다리)
수를 나란히 쓰고 모두 나눠지는 소수로 계속 나눠요. 더 이상 함께 나눠지지 않으면 멈추고, 왼쪽에 쓴 수를 모두 곱하면 최대공약수, 왼쪽 수와 맨 아래 남은 수까지 모두 곱하면 최소공배수예요. 초등·중학교 교과서에서 가장 많이 쓰는 방법이에요.
③ 유클리드 호제법
공식은 gcd(a, b) = gcd(b, a mod b), 나머지가 0이 되면 그때 나눈 수가 최대공약수예요. 수가 커도 몇 단계면 끝나서 컴퓨터도 이 방법을 써요. 최소공배수는 lcm(a, b) = a × b ÷ gcd(a, b)로 구해요.
예시 계산 3가지
| 수 | 풀이 | 최대공약수 · 최소공배수 |
|---|---|---|
| ① 24, 36, 60 | 24 = 2³ × 3, 36 = 2² × 3², 60 = 2² × 3 × 5 → 공통 2² × 3, 전체 2³ × 3² × 5 | 12 · 360 |
| ② 84, 126 | 사다리: 2 ) 84 126 → 3 ) 42 63 → 7 ) 14 21 → 2 3 (서로소) | 2 × 3 × 7 = 42 · 42 × 2 × 3 = 252 |
| ③ 1071, 1029 | 1071 = 1029 × 1 + 42 → 1029 = 42 × 24 + 21 → 42 = 21 × 2 + 0 | 21 · 1071 × 1029 ÷ 21 = 52,479 |
문장제: 최대공약수일까, 최소공배수일까
| 문제에 나오는 말 | 쓰는 것 | 예 |
|---|---|---|
| "가능한 한 많은 사람에게 똑같이 나누기", "가장 큰 정사각형으로 자르기" | 최대공약수 | 사탕 24개·초콜릿 36개를 남김없이 똑같이 나눌 최대 인원 → 12명 |
| "동시에 다시 출발", "처음으로 다시 만나는", "가장 작은 정사각형 만들기" | 최소공배수 | 12분·18분 간격 버스가 다시 동시에 오는 때 → 36분 뒤 |
타일 문제도 같아요. 가로 84cm·세로 126cm 벽에 같은 크기 정사각형 타일을 빈틈없이 붙일 때 가장 큰 타일 한 변은 최대공약수 42cm, 필요한 타일은 (84 ÷ 42) × (126 ÷ 42) = 6장이에요.
알아 두면 좋은 성질
- 두 수 A, B에 대해 A × B = 최대공약수 × 최소공배수예요. 12 × 18 = 216 = 6 × 36이에요.
- 서로소의 최소공배수는 두 수의 곱이에요. 8과 15의 최소공배수는 120이에요.
- 공약수는 모두 최대공약수의 약수이고, 공배수는 모두 최소공배수의 배수예요.
- 세 수 이상은 앞의 두 수 결과와 다음 수를 차례로 계산해요. gcd(24, 36, 60) = gcd(gcd(24, 36), 60) = gcd(12, 60) = 12예요.
소인수분해를 빨리 하는 나눗셈 판별법
| 나누는 수 | 나누어떨어지는 조건 | 예 |
|---|---|---|
| 2 | 일의 자리가 짝수 | 126 → 6 |
| 3 | 각 자리 숫자 합이 3의 배수 | 1071 → 1+0+7+1 = 9 |
| 4 | 끝 두 자리가 4의 배수 | 1,036 → 36 |
| 5 | 일의 자리가 0 또는 5 | 60, 125 |
| 9 | 각 자리 숫자 합이 9의 배수 | 1071 → 9 |
| 11 | 홀수째 자리 합과 짝수째 자리 합의 차가 11의 배수(0 포함) | 1,331 → (1+3) − (3+1) = 0 |
약수 개수 구하는 공식
N = pa × qb × rc로 소인수분해되면 약수 개수는 (a + 1) × (b + 1) × (c + 1)이에요. 360 = 2³ × 3² × 5라서 (3 + 1) × (2 + 1) × (1 + 1) = 24개예요. 공약수 개수는 최대공약수의 약수 개수와 같아서, 12와 18의 공약수는 최대공약수 6 = 2 × 3의 약수 2 × 2 = 4개(1, 2, 3, 6)예요.
활용 문제 풀이
- 톱니바퀴 — 톱니 24개와 36개인 두 바퀴가 맞물려 돌 때, 처음 맞물린 톱니가 다시 만나려면 톱니 lcm(24, 36) = 72개가 지나가야 해요. 작은 바퀴는 72 ÷ 24 = 3바퀴, 큰 바퀴는 72 ÷ 36 = 2바퀴 돌아요.
- 정육면체 쌓기 — 가로 6cm, 세로 8cm, 높이 10cm 상자를 같은 방향으로 쌓아 가장 작은 정육면체를 만들면 한 변은 lcm(6, 8, 10) = 120cm예요. 상자는 20 × 15 × 12 = 3,600개가 필요해요.
- 똑같이 나누기 — 연필 48자루와 공책 72권을 남김없이 똑같이 나눠 줄 최대 인원은 gcd(48, 72) = 24명이고, 한 명당 연필 2자루·공책 3권이에요.
유클리드 호제법이 빠른 이유
나머지는 항상 나누는 수보다 작아서, 두 단계마다 수가 절반 아래로 줄어요. 그래서 15자리 수라도 수십 단계 안에 끝나요. 반대로 약수를 하나씩 찾는 방법은 수가 커질수록 시간이 크게 늘어요.
프로그래밍에서도 같은 원리로 한 줄이면 돼요. 자바스크립트라면 const gcd = (a, b) => b ? gcd(b, a % b) : a;, 최소공배수는 a / gcd(a, b) * b예요. 곱하기 전에 먼저 나누면 큰 수에서 넘침(overflow)을 줄일 수 있어요.
결과 읽는 법
- 큰 숫자는 최대공약수, 아래 줄은 최소공배수예요. 서로소면 "서로소"라고 함께 표시돼요.
- 소인수분해 행은 입력한 수마다 하나씩 나오고, 공약수는 60개까지 보여 줘요.
- 풀이는 숫자가 6개 이하면 사다리, 2개면 유클리드 호제법까지 나와요. 숙제 검산에 그대로 쓸 수 있어요.
흔한 실수
- 세 수의 최소공배수를 두 수 공식으로 구하기 — 6, 8, 10은 6 × 8 × 10 ÷ 2 = 240이 아니라 120이에요. A × B = GCD × LCM 성질은 두 수일 때만 맞아요.
- 사다리에서 두 수만 나눠지는 수로 멈추기 — 세 수 사다리에서 최대공약수는 세 수가 모두 나눠지는 단계까지만 곱해요. 최소공배수는 두 수만 나눠져도 계속 나눠야 해요.
- 1을 소수로 보기 — 1은 소수가 아니라서 소인수분해에 쓰지 않아요. 가장 작은 소수는 2예요.
- 최대공약수 문제에 최소공배수 쓰기 — "나누기·자르기"는 작아지는 문제라 최대공약수, "다시 만나기·쌓기"는 커지는 문제라 최소공배수예요.
- 최대공약수가 최소공배수보다 크게 나오는 답 — 최대공약수는 항상 가장 작은 수 이하, 최소공배수는 가장 큰 수 이상이에요. 이 범위를 벗어나면 계산을 다시 확인하세요. 12와 18이라면 최대공약수는 12 이하, 최소공배수는 18 이상이어야 해요.
BigInt로 계산해 15자리 수도 정확해요. 입력값은 브라우저 밖으로 나가지 않아요.