실제로 언제 쓰나
소인수분해는 학교 시험이나 코딩 테스트에만 나오는 개념처럼 보이지만, 실생활에서도 은근히 자주 필요합니다. 물건 36개를 남김없이 똑같이 나눠 담을 상자 개수를 정할 때(약수 찾기), 두 가지 반복 주기(예: 15일 배송 주기와 20일 청소 주기)가 같은 날 겹치는 다음 날짜를 구할 때(최소공배수), 분수를 최대한 간단히 약분할 때(최대공약수) 모두 소인수분해가 바탕에 깔려 있습니다. 정보처리기사·코딩테스트 준비생에게는 유클리드 호제법과 함께 가장 기본적인 알고리즘이기도 합니다.
계산법 — 작은 소수부터 나눠보는 것
소인수분해는 어떤 정수를 소수(1과 자기 자신으로만 나눠지는 수)들의 곱으로 표현하는 것입니다. 계산 방법은 단순합니다. 가장 작은 소수인 2부터 시작해 나눠지는 만큼 계속 나누고, 더는 나눠지지 않으면 다음 소수(3, 5, 7…)로 넘어갑니다. 이 과정을 나눈 값이 1이 될 때까지 반복하면 끝입니다.
실수하기 쉬운 지점은 1을 소수로 착각하는 것입니다. 1은 약수가 자기 자신 하나뿐이라 소수의 정의(약수가 정확히 2개)에 맞지 않아 소수도 합성수도 아닙니다. 또한 짝수를 2로 여러 번 나누다가 홀수가 남으면 다음은 3부터 다시 시도해야 하는데, 이미 2로 나눠 떨어진 값에서 4로 나눠지는지 확인하는 실수도 흔합니다. 4는 이미 2×2로 걸러졌으므로 소인수가 될 수 없습니다.
작은 소수 판별 기준표
| 확인 범위 | 나눠봐야 할 소수 | 비고 |
|---|---|---|
| ~100 | 2, 3, 5, 7 | 제곱근이 10 이하이므로 이 4개만 확인하면 충분 |
| ~1,000 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 | 제곱근(약 31.6) 이하 소수까지 확인 |
| ~10,000 | 2~97 사이 소수 25개 | 제곱근(100) 이하 소수까지 확인 |
어떤 수 N이 소수인지 확인할 때 N의 제곱근보다 큰 수로는 나눠볼 필요가 없습니다. 제곱근보다 큰 약수가 있다면 반드시 그와 짝을 이루는 제곱근보다 작은 약수도 존재하기 때문입니다. 이 원리 덕분에 큰 수를 손으로 확인할 때도 계산량이 크게 줄어듭니다.
최대공약수·최소공배수와의 관계
두 수의 최대공약수(GCD)는 각 수의 소인수분해에서 공통으로 들어간 소인수를 가장 작은 지수로 곱한 값이고, 최소공배수(LCM)는 두 수에 등장하는 모든 소인수를 가장 큰 지수로 곱한 값입니다. 예를 들어 12=2²×3, 18=2×3²일 때 GCD는 공통 소인수 2¹×3¹=6이고, LCM은 2²×3²=36입니다. 이 계산기의 '숫자 2개' 모드는 유클리드 호제법으로 GCD를 먼저 구하고, GCD×LCM이 두 수의 곱과 같다는 성질을 이용해 LCM을 구합니다.
소인수분해로 약수 개수 구하기
소인수분해를 알면 어떤 수의 약수가 총 몇 개인지도 일일이 나눠보지 않고 바로 구할 수 있습니다. 소인수분해했을 때 지수가 각각 a, b, c…라면, 약수 개수는 (a+1)×(b+1)×(c+1)…로 계산합니다. 예를 들어 84=2²×3¹×7¹이므로 약수 개수는 (2+1)×(1+1)×(1+1)=3×2×2=12개입니다. 실제로 84의 약수를 나열하면 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84로 정확히 12개입니다.
| 숫자 | 소인수분해 | 약수 개수 계산 | 약수 개수 |
|---|---|---|---|
| 84 | 2²×3¹×7¹ | (2+1)×(1+1)×(1+1) | 12개 |
| 100 | 2²×5² | (2+1)×(2+1) | 9개 |
| 360 | 2³×3²×5¹ | (3+1)×(2+1)×(1+1) | 24개 |
이 공식은 물건을 똑같은 개수로 나눌 수 있는 상자 크기의 경우의 수를 셀 때, 또는 '약수의 개수가 홀수인 수는 완전제곱수뿐'이라는 성질을 확인할 때처럼, 하나하나 나눠보지 않고도 구조를 파악하는 데 쓰입니다.
사례로 끝까지 계산하기
84를 소인수분해해 보겠습니다. 84는 짝수이므로 2로 나누면 42, 다시 2로 나누면 21이 되어 더는 2로 나눠지지 않습니다. 21은 3으로 나누면 7이 되고, 7은 소수이므로 여기서 멈춥니다. 결과는 84 = 2 × 2 × 3 × 7, 지수 표기로는 2² × 3 × 7입니다.
이번엔 84와 18의 GCD·LCM을 구해보겠습니다. 18=2×3²입니다. 두 수의 공통 소인수는 2¹과 3¹이므로 GCD=2×3=6입니다. LCM은 두 수의 곱(84×18=1,512)을 GCD(6)로 나눈 1,512÷6=252입니다. 실제로 252는 84의 배수(84×3)이자 18의 배수(18×14)이므로 검산이 맞습니다.
큰 수로 갈수록 어려워지는 이유 — 암호학과의 연결
이 계산기는 2 이상 1억 이하의 정수를 대상으로 합니다. 시행착오 나눗셈(trial division) 방식은 숫자가 커질수록, 특히 그 수가 큰 소수이거나 두 개의 큰 소수의 곱일 때 계산 시간이 크게 늘어납니다. 1억 이하에서는 제곱근(최대 1만 정도)까지만 확인하면 되지만, 자릿수가 늘어날수록 확인해야 할 소수의 개수가 훨씬 빠르게 늘어나기 때문입니다.
두 수를 곱하기는 쉽지만 곱한 결과를 다시 원래 두 수로 쪼개기는 어렵다는 이 비대칭성은 실생활 보안 기술의 기초이기도 합니다. 인터넷 결제나 로그인에 쓰이는 RSA 공개키 암호 방식은 수백 자리에 이르는 두 개의 큰 소수를 곱한 값을 공개키로 사용합니다. 곱셈 자체는 컴퓨터가 순식간에 처리하지만, 그 곱을 원래의 두 소수로 되돌리는 소인수분해는 현재까지 알려진 방법으로는 현실적인 시간 안에 풀 수 없을 만큼 오래 걸립니다. 이 계산기가 다루는 1억 이하의 수는 그런 암호학적 규모와는 비교가 안 될 만큼 작지만, 숫자가 커질수록 소인수분해가 기하급수적으로 어려워진다는 원리는 동일합니다.
시험이나 일상적인 약수·배수 계산에는 이 계산기의 범위로 충분하며, 억 단위를 넘는 큰 수나 암호학 수준의 소인수분해에는 이런 단순 방식이 아니라 훨씬 정교한 전용 알고리즘이 필요합니다.