홍라이프 계산기약수 구하기 쉽게 이해하기 — 개념과 원리
자연수 n의 약수는 n을 나머지 없이 나누어떨어지게 하는 모든 자연수입니다. 이 계산기는 약수를 작은 순서로 나열하고, 개수와 합을 구하며, n이 완전수, 과잉수, 부족수 가운데 어디에 속하는지도 알려 줍니다. 물건을 같은 개수씩 줄 세우거나, 모둠 인원을 정하거나, 분수를 약분하거나, 수 퍼즐을 풀 때 쓰입니다.
계산 방법
- i를 1부터 i × i ≤ n인 동안 늘려 가며 n이 i로 나누어떨어지는지 확인합니다.
- 나누어떨어지면 i와 n ÷ i가 모두 약수입니다. i × i = n이면 두 수가 같으므로 하나만 셉니다.
- 약수를 정렬해 개수를 세고, n 자신을 포함한 모든 약수의 합을 구합니다.
- 자기 자신을 뺀 약수의 합(약수의 합 − n)을 n과 비교해, 같으면 완전수, 크면 과잉수, 작으면 부족수로 분류합니다.
입력값은 1부터 10¹²까지의 자연수입니다.
원리
약수는 i × (n ÷ i) = n처럼 짝을 이루고, 각 짝 가운데 하나는 반드시 √n 이하입니다. 그래서 √n까지만 확인해도 모든 약수를 찾을 수 있고, n = 10¹²이라도 1조 번이 아니라 약 100만 번만 확인하면 됩니다. n = p₁^e₁ × p₂^e₂ × …로 소인수분해되면 약수의 개수는 (e₁ + 1)(e₂ + 1)…이므로 목록의 길이를 검산할 수 있습니다. 완전수와 과잉수, 부족수의 구분은 고대 그리스 수학에서 비롯되었습니다.
예제 풀이
- 입력값: 72이고, √72 ≈ 8.49이므로 i = 1부터 8까지 확인합니다.
- 찾은 짝은 1 × 72, 2 × 36, 3 × 24, 4 × 18, 6 × 12, 8 × 9입니다. 5와 7은 약수가 아닙니다.
- 정렬하면 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72이고 개수는 12개입니다. 72 = 2³ × 3²이므로 (3 + 1)(2 + 1) = 12로 검산됩니다.
- 약수의 합은 195입니다.
- 자기 자신을 뺀 약수의 합은 195 − 72 = 123으로 72보다 크므로 과잉수(abundant)입니다.
| 숫자 | 개수 |
|---|---|
| 18 | 6 |
| 36 | 9 |
| 54 | 8 |
| 72 | 12 |
| 90 | 12 |
| 108 | 12 |
| 144 | 15 |
결과 해석
약수의 개수가 홀수이면 n은 제곱수입니다. 제곱근이 자기 자신과 짝을 이루기 때문입니다. 소수는 약수가 정확히 두 개입니다. 대부분의 수는 부족수이며, 가장 작은 과잉수는 12이고, 10,000보다 작은 완전수는 6, 28, 496, 8128뿐입니다. 60, 72, 360처럼 크기에 비해 약수가 많은 수는 여러 방법으로 똑같이 나누기 좋습니다.
흔한 실수
- 1과 n 자신을 빠뜨립니다. 이 둘은 언제나 약수입니다.
- √n까지 확인하지 않고 일찍 멈추어 짝을 놓칩니다.
- 완전수 판별에 n을 포함한 약수의 합을 그대로 씁니다. 자기 자신을 뺀 합과 비교해야 합니다.
자주 묻는 질문
제곱수의 약수 개수는 왜 홀수인가요?
약수는 i와 n ÷ i로 짝을 짓는데, √n은 자기 자신과 짝이 되어 하나가 남기 때문입니다.
홀수인 완전수도 있나요?
지금까지 발견된 것은 없습니다. 존재 여부는 아직 풀리지 않은 유명한 문제이며, 알려진 완전수는 모두 짝수입니다.
음수에도 약수가 있나요?
−2도 72를 나누지만, 약수를 나열할 때는 관례적으로 자연수만 씁니다.
출처: Euclid, Elements, Book VII 정의, Book IX 명제 36(짝수 완전수) · G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Chapter 16