C++でアリコート和（Aliquot Sum）を計算する方法

本記事では、アリコート和（Aliquot Sum）とは何かを解説します。アリコート和とは、ある数 n の約数のうち、n 自身を除いたすべての約数の総和のことです。例えば、数値が 20 の場合、その約数は (1, 2, 4, 5, 10) となるため、アリコート和は 22 になります。

興味深い点として、アリコート和がその数自身と等しくなる場合、その数は「完全数」と呼ばれます。例えば 6 の場合、約数は (1, 2, 3) であり、アリコート和は 1 + 2 + 3 = 6 となるため、6 は完全数です。

それでは、以下のアルゴリズムを使ってアリコート和を求める方法を見ていきましょう。

アルゴリズム

getAliquotSum(n)

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

C++での実装例

以下は、C++でアリコート和を計算するサンプルプログラムです。1 から n-1 までの数値を順に調べ、n を割り切れるもの（約数）を合計しています。

#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 << "Enter a number to get Aliquot sum: ";
    cin >> n;
    cout << "The Aliquot sum of " << n << " is " << getAliquotSum(n);
}

実行結果

Enter a number to get Aliquot sum: 20
The Aliquot sum of 20 is 22

このプログラムでは、入力として 20 を与えると、約数 (1, 2, 4, 5, 10) の総和である 22 が出力されます。なお、この実装の計算量は O(n) ですが、約数を √n まで調べてペアで加算する方法を使えば、より効率的に O(√n) まで計算量を抑えることも可能です。