세상의 모든 유틸계산 방법
최대공약수: 유클리드 호제법
두 수 a, b(a ≥ b)에서 a를 b로 나눈 나머지를 r이라 하면 gcd(a, b) = gcd(b, r)입니다. 나머지가 0이 될 때까지 반복하면 마지막으로 나눈 수가 최대공약수입니다. 예: gcd(1071, 462) → 1071 = 2 × 462 + 147 → 462 = 3 × 147 + 21 → 147 = 7 × 21 + 0, 따라서 21입니다. 소인수분해 없이 나눗셈만 쓰므로 수백 자리 수도 순식간에 계산됩니다.
최소공배수
lcm(a, b) = |a × b| ÷ gcd(a, b)입니다. 곱이 너무 커지지 않도록 a ÷ gcd를 먼저 한 뒤 b를 곱합니다. 세 수 이상은 lcm(lcm(a, b), c)처럼 차례로 구합니다. 두 수의 최대공약수와 최소공배수를 곱하면 항상 두 수의 곱(절댓값)과 같습니다.
소인수분해와 소수 판정
먼저 1만 이하의 소수로 나눠 작은 소인수를 떼어 내고, 남은 수가 소수인지 밀러–라빈 판정으로 확인합니다. 합성수이면 폴라드 로(Pollard rho) 알고리즘으로 약수를 찾아 계속 쪼갭니다. 모든 계산은 자바스크립트 BigInt 정수로 하므로 2⁵³(약 9,007조)을 넘는 수도 반올림 없이 정확합니다.
최대공약수·최소공배수 예시
| 수 | 최대공약수 | 최소공배수 |
|---|---|---|
| 12, 18 | 6 | 36 |
| 8, 12, 20 | 4 | 120 |
| 48, 180 | 12 | 720 |
| 24, 36, 60 | 12 | 360 |
| 17, 31 | 1 | 527 |
| 360, 840 | 120 | 2,520 |
| 1071, 462 | 21 | 23,562 |
| 2, 3, 4, 5, 6, 7, 8, 9, 10 | 1 | 2,520 |
소인수분해 예시
| 수 | 소인수분해 | 약수 개수 | 소수 |
|---|---|---|---|
| 12 | 2² × 3 | 6 | 합성수 |
| 60 | 2² × 3 × 5 | 12 | 합성수 |
| 360 | 2³ × 3² × 5 | 24 | 합성수 |
| 1,024 | 2¹⁰ | 11 | 합성수 |
| 2,026 | 2 × 1013 | 4 | 합성수 |
| 9,973 | 9973 | 2 | 소수 |
| 720,720 | 2⁴ × 3² × 5 × 7 × 11 × 13 | 240 | 합성수 |
| 600,851,475,143 | 71 × 839 × 1471 × 6857 | 16 | 합성수 |
| 9,007,199,254,740,991 | 6361 × 69431 × 20394401 | 8 | 합성수 |
표는 페이지를 만들 때 위 계산기와 같은 코드로 계산했습니다. 9,007,199,254,740,991은 자바스크립트 일반 숫자로 정확히 다룰 수 있는 가장 큰 정수(2⁵³ − 1)입니다.
0과 음수 처리 규칙
- 음수는 절댓값으로 계산합니다. gcd(−12, 18) = 6, lcm(−4, 6) = 12.
- gcd(0, n) = |n|. 모두 0이면 최대공약수는 0으로 표시합니다.
- 0이 하나라도 있으면 최소공배수는 0입니다(0은 모든 수의 배수).
- 소수는 2 이상의 자연수에서만 따집니다. 0, 1, 음수는 소수가 아닙니다.
- 소수(1.5)나 분수는 넣을 수 없습니다. 분수의 약분·통분은 분수 계산기를 이용하세요.