JavaScriptで完全数を判定する方法｜効率的なアルゴリズムとコード例

完全数とは？

完全数（かんぜんすう）とは、その数自身を除く正の約数の総和が、元の数と等しくなる正の整数のことです。ここでいう約数とは、ある整数 x を余りなく割り切ることができる整数を指します。

例えば、28 は完全数です。

28 is a perfect number, because
28 = 1 + 2 + 4 + 7 + 14

1、2、4、7、14 はいずれも 28 を割り切ることができ、その合計がちょうど 28 になるためです。

この記事では、数値 n を受け取り、n が完全数であるかどうかを判定する JavaScript 関数を作成します。

実装のポイント：なぜ √n まで調べればよいのか

単純に 1 から n−1 までのすべての数で割り切れるかを確認することもできますが、この方法は計算量が O(n) となり非効率です。

約数には「i × j = n」という形でペアで現れるという性質があります。たとえば 28 の場合、「2 × 14」「4 × 7」のように、片方の約数が分かればもう片方も自動的に求まります。この性質を利用すれば、√n まで調べるだけで済み、計算量を O(√n) にまで削減できます。

コード例

const num = 28;

const checkPerfectNumber = (num = 1) => {
   // 完全数は 1 より大きい数なので、1 は除外する
   if(num === 1) {
      return false;
   };
   // 1 はすべての数の約数なので、最初から加算しておく
   let sum = 1;
   for(let i = 2; i <= Math.floor(Math.sqrt(num)); i++){
      // i が約数なら、ペアとなる (num / i) も一緒に加算
      if(num % i === 0) {
         sum = sum + i + num / i;
         // 合計が既に num を超えていたら、完全数ではない
         if(sum > num) {
            return false;
         }
      };
   };
   return sum === num;
};

console.log(checkPerfectNumber(num));

出力結果

コンソールには次のように表示されます。

true

コードの解説

• num === 1 のチェック： 自身を除く約数を持たないため、1 は定義上、完全数になりません。そのため最初に false を返します。
• sum を 1 で初期化： 1 はすべての正の整数の約数であるため、ループ前に合計へ加算しておきます。
• √num までループ： 約数はペア（i と num / i）で現れるため、平方根まで確認すれば全ての約数を網羅できます。
• 早期リターン： 合計が num を超えた時点で完全数である可能性が消えるため、無駄な処理を省いて即座に false を返します。

参考：知られている完全数

完全数は非常に稀な数として知られています。小さい方から順に、以下のようなものが挙げられます。

• 6 ＝ 1 + 2 + 3
• 28 ＝ 1 + 2 + 4 + 7 + 14
• 496
• 8128

これらの数を checkPerfectNumber 関数に渡せば、いずれも true が返されることを確認できます。ぜひ試してみてください。