C++でほぼ完全数（Almost Perfect Number）を判定する方法

ほぼ完全数（Almost Perfect Number）とは？

ほぼ完全数（Almost Perfect Number）は、「最小不足数（least deficient number）」や「わずかに不足した数（slightly defective number）」とも呼ばれる特殊な数です。その約数の総和（1とその数自身を含む）が 2n-1 に等しくなる数を指します。

本記事では、与えられた数がほぼ完全数であるかどうかを判定するアルゴリズムを、具体例を交えながら解説します。

具体例で理解する

まず、例を見ながら概念を確認しましょう。

入力：16
出力：Yes
説明：
16の約数は 1, 2, 4, 8, 16 です。
合計 = 1 + 2 + 4 + 8 + 16 = 31
n = 16 のとき、2n-1 = 2×16 - 1 = 31

入力：12
出力：No
説明：
12の約数は 1, 2, 3, 4, 6, 12 です。
合計 = 1 + 2 + 3 + 4 + 6 + 12 = 26
n = 12 のとき、2n-1 = 2×12 - 1 = 23

16の場合、約数の総和が 2n-1 と一致するためほぼ完全数ですが、12の場合は総和が 2n-1 より大きいため、ほぼ完全数ではありません。このように、約数の総和が 2n-1 と一致するかどうかを確認することで判定できます。

アルゴリズム

判定の手順は以下の通りです。

ステップ1：その数のすべての約数の総和を計算する。
ステップ2：val = 2n-1 の値を計算する。
ステップ3：sum == val の場合 →「YES」と出力する。
ステップ4：それ以外の場合 →「NO」と出力する。

C++での実装例

#include <iostream>
using namespace std;
void almostPerfectNumber(int n);
int main(){
    int n = 16;
    cout<<"Is "<<n<<" an almost perfect number ?\n";
    almostPerfectNumber(n);
}
void almostPerfectNumber(int n){
    int divisors = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0)
            divisors += i;
    }
    if (divisors == 2 * n - 1)
        cout<<"YES";
    else
        cout<<"NO";
}

出力結果

Is 16 an almost perfect number ?
YES

このプログラムでは、1からnまでの数を順に確認し、nを割り切れる数（約数）をすべて合計しています。その合計が 2n-1 と一致すれば「YES」、一致しなければ「NO」を出力します。

補足：計算量を改善するには

上記の実装は計算量が O(n) ですが、約数はペアで現れる（i と n/i の組み合わせ）という性質を利用すると、√n まで調べるだけでよいため、計算量を O(√n) まで改善できます。大きな数を扱う場合にはこちらの方法が効率的です。

なお、数学的に興味深い点として、2のべき乗（1, 2, 4, 8, 16, ...）はすべてほぼ完全数であることが知られています。一方、奇数のほぼ完全数が存在するかどうかは、未解決の問題となっています。