C 프로그래밍으로 초완전수(Super Perfect Number) 판별하기

초완전수란 무엇일까요?

초완전수(super perfect number)는 완전수(perfect number)와 매우 유사한 개념입니다. 1969년 D. 수리야나라야나(D. Suryanarayana)에 의해 발견되었으며, 다음 공식을 만족하는 수로 정의됩니다.

sig(sig(n)) = 2n

여기서 sig(n)은 어떤 수의 약수 전체의 합을 계산하는 함수로, '약수 합 함수(divisor summatory function)'라고도 불립니다.

초완전수 판별 예시

개념을 더 명확히 이해하기 위해 실제 예시를 살펴보겠습니다. 주어진 수 N이 초완전수인지 판별해야 한다고 가정해 봅시다.

N = 16

출력 결과

yes

풀이 과정 — 어떤 수가 초완전수인지 확인하려면 먼저 그 수의 약수의 합을 구하고, 다시 그 합의 약수의 합을 한 번 더 구하면 됩니다.

sig(16) = 1 + 2 + 4 + 8 + 16 = 31 (16의 약수는 1, 2, 4, 8, 16)
sig(31) = 1 + 31 = 32 (31은 소수이므로 약수가 1과 자기 자신뿐)
2 × n = 32 = sig(sig(n))

계산 결과 sig(sig(n)) = 2n 조건을 만족하므로, 16은 초완전수입니다.

초완전수가 아닌 경우

이번에는 초완전수가 아닌 수의 예를 살펴보겠습니다.

n = 6
sig(6) = 1 + 2 + 3 + 6 = 12
sig(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28
6 × 2 = 12 ≠ 28

6은 완전수이기는 하지만, 두 번의 약수 합 계산 결과가 2n과 일치하지 않으므로 초완전수는 아닙니다.

C 언어 구현 코드

이제 위 개념을 C 프로그램으로 구현해 보겠습니다. 약수의 합을 효율적으로 구하기 위해 √n까지만 반복하는 방식을 사용합니다.

#include<stdio.h>
// num의 약수의 합을 구하는 함수
int divisorsum(int n){
    int sum = 0; // 합 초기화
    for (int i=1; i*i <= n; ++i){
        if (n%i == 0) { // 약수를 찾아 합산
            if (i == (n/i))
                sum += i;
            else
                sum += (i + n/i);
        }
    }
    return sum;
}
int main() {
    int n = 16;
    int n1 = divisorsum(n);
    if(2*n == divisorsum(n1)){
        printf("The number %d is a superperfect number", n);
    } else{
        printf("The number %d is not a superperfect number", n);
    }
    return 0;
}

실행 결과

The number 16 is a super perfect number

프로그램을 실행하면 16이 초완전수임을 정확히 판별하는 것을 확인할 수 있습니다. 이처럼 약수 합 함수를 두 번 적용한 결과가 원래 수의 2배와 같은지만 비교하면, 어떤 수든 손쉽게 초완전수 여부를 검사할 수 있습니다.