C++로 알리쿼트 합(Aliquot Sum) 구하는 방법

알리쿼트 합(Aliquot Sum)이란?

알리쿼트 합은 어떤 수 n의 약수 중에서 자기 자신을 제외한 나머지 약수(진약수)를 모두 더한 값입니다. 예를 들어 숫자가 20이라면, 20의 진약수는 (1, 2, 4, 5, 10)입니다. 따라서 알리쿼트 합은 1+2+4+5+10 = 22가 됩니다.

여기서 흥미로운 사실 하나! 어떤 수의 알리쿼트 합이 그 수 자신과 같다면, 그 수를 완전수(perfect number)라고 부릅니다. 대표적인 예가 바로 6입니다. 6의 진약수는 (1, 2, 3)이며, 알리쿼트 합은 1+2+3 = 6으로 자기 자신과 같습니다.

그럼 아래 알고리즘을 통해 알리쿼트 합을 구하는 방법을 살펴보겠습니다.

알고리즘

getAliquotSum(n)

begin
    sum := 0
    for i in range 1 to n-1, do
        if n is divisible by i, then
            sum := sum + i
        end if
    done
    return sum.
end

C++ 구현 예제

#include <iostream>
using namespace std;

int getAliquotSum(int n) {
    int sum = 0;
    for(int i = 1; i < n; i++) {
        if(n % i == 0) {
            sum += i;
        }
    }
    return sum;
}

int main() {
    int n;
    cout << "알리쿼트 합을 구할 숫자를 입력하세요: ";
    cin >> n;
    cout << n << "의 알리쿼트 합은 " << getAliquotSum(n);
}

실행 결과

알리쿼트 합을 구할 숫자를 입력하세요: 20
20의 알리쿼트 합은 22

성능 개선 팁