과잉수(Abundant Number)란?
과잉수는 수론(number theory)에서 다루는 개념으로, 자기 자신을 제외한 모든 진약수의 합이 자기 자신보다 큰 수를 의미합니다. '풍부한 수' 또는 '과대수'라고도 부릅니다.
가장 대표적인 예는 12입니다. 12의 약수는 1, 2, 3, 4, 6, 12이고, 자기 자신을 뺀 진약수는 1, 2, 3, 4, 6입니다. 이들의 합은 16으로 12보다 크므로, 12는 과잉수입니다.
참고로 과잉수는 12, 18, 20, 24, 30, 36처럼 주로 짝수에서 나타나며, 홀수 과잉수 중 가장 작은 수는 945입니다.
과잉분(Abundance)
진약수의 합에서 원래 수를 뺀 값, 즉 그 차이를 과잉분(abundance)이라고 합니다. 12의 경우 과잉분은 다음과 같이 계산됩니다.
과잉분 = 16 − 12 = 4
C 언어로 과잉수 판별하기
어떤 수가 과잉수인지 확인하는 방법은 간단합니다. 해당 수의 모든 약수를 구해 합산한 뒤, 그 합을 원래 수와 비교하면 됩니다.
여기서는 효율성을 위해 1부터 √n까지만 검사합니다. i가 n의 약수라면 n/i 역시 약수이므로, 두 값을 함께 더하면 √n보다 큰 약수까지 놓치지 않고 처리할 수 있습니다. 마지막에 자기 자신(n)을 빼주면 진약수의 합만 남게 되며, 이 값이 n보다 큰지 비교하여 과잉수 여부를 판단합니다.
예제 코드
#include <stdio.h>
#include <math.h>
int main() {
int n = 56, sum = 0;
// 1부터 √n까지 검사하여 약수의 합을 구함
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
if (n / i == i) { // i가 n의 제곱근인 경우
sum += i; // 중복되지 않도록 한 번만 더함
} else { // 약수 쌍 (i, n/i)을 함께 더함
sum += i;
sum += n / i;
}
}
}
sum -= n; // 자기 자신을 제외하여 진약수의 합만 계산
if (sum > n) {
printf("%d는 과잉수입니다.\n", n);
} else {
printf("%d는 과잉수가 아닙니다.\n", n);
}
return 0;
}실행 결과
56는 과잉수입니다.
코드 동작 원리
n = 56일 때 프로그램의 실행 흐름은 다음과 같습니다.
- i = 1 → 약수 쌍 (1, 56) 발견 → sum = 57
- i = 2 → 약수 쌍 (2, 28) 발견 → sum = 87
- i = 4 → 약수 쌍 (4, 14) 발견 → sum = 105
- i = 7 → 약수 쌍 (7, 8) 발견 → sum = 120
전체 약수의 합은 120이고, 여기서 자기 자신인 56을 빼면 진약수의 합은 64가 됩니다. 64 > 56이므로 프로그램은 56이 과잉수라고 출력합니다.
마무리
과잉수 판별은 약수의 성질을 활용하는 기본적인 수론 문제입니다. √n까지만 반복문을 돌리는 최적화 기법을 익혀두면 완전수(perfect number)나 부족수(deficient number) 판별 같은 유사한 문제에도 그대로 응용할 수 있습니다.