C++で完全数を判定する方法をわかりやすく解説

完全数とは？

完全数（Perfect Number）とは、その数自身を除くすべての正の約数の総和が、元の数とちょうど等しくなるような自然数のことです。
例えば 28 の場合、約数は 1、2、4、7、14 であり、その和は 1 + 2 + 4 + 7 + 14 = 28 となるため、28 は完全数であると言えます。

問題の概要

与えられた整数が完全数かどうかを判定するプログラムを作成します。判定対象となる数 n の範囲は 10⁸（1億）以下とします。入力が 28 であれば、出力は True となります。

解法のアプローチ

ここで重要なポイントは、10⁸ 以下の範囲に存在する完全数はごくわずかだという点です。具体的には、次の5つだけです。

• 6
• 28
• 496
• 8128
• 33550336

これは「偶数の完全数は 2^p−1 × (2^p − 1) の形で表される」というオイラーの定理に関連する性質によるもので、この範囲内では他に完全数は存在しません。

したがって、入力のたびに約数を列挙して合計を計算する必要はなく、あらかじめ既知の完全数を集合（set）として用意しておき、入力値がその集合に含まれているかどうかを確認するだけで高速に判定できます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool checkPerfectNumber(int num) {
        set<int> set={6,28,496,8128,33550336};
        return set.find(num)!=set.end();
    }
};
main(){
    Solution ob;
    cout << (ob.checkPerfectNumber(28));
}

実行結果

入力

28

出力

1

コードのポイント

この実装では、STL の set コンテナに既知の完全数を格納し、find メソッドを使って入力値が存在するかどうかを確認しています。要素が見つかれば true（出力では 1）、見つからなければ false（0）が返されます。
集合の探索は対数時間 O(log n) で行えるため、約数をすべて求める方法（O(√n)）よりもシンプルかつ高速に処理できるのが大きな利点です。