C++で数値が2つの過剰数の和として表現できるか判定する方法

ある整数 n が与えられたとき、それを2つの過剰数の和として表現できるかどうかを判定します。表現できる場合はその2つの数を出力し、できない場合は -1 を出力します。

ここで「過剰数（Abundant Number）」とは、その数自身を除く約数（真の約数）の総和 sum(n) が、元の数の値より大きくなるような数のことです。例えば 12 の真の約数は 1, 2, 3, 4, 6 で、その総和は 16 となり 12 より大きいため、12 は過剰数です。

解法のアプローチ

この問題を解くには、まず N 未満のすべての過剰数をあらかじめセット（set）に格納しておきます。次に、与えられた数 n に対して i = 1 から n までループを回し、「i と (n − i) がどちらも過剰数である」ような組み合わせが存在するかを確認します。

約数の総和は効率的に求められます。2 から √i までの各 j について i が j で割り切れるならば、j と i/j を約数として加算します（j = i/j の場合、つまり完全平方数の場合は二重カウントを避けるため一度だけ加算します）。初期値として 1 を加えておくことで、i 自身を除くすべての約数の総和が得られます。

C++での実装例

#include <iostream>
#include <set>
#define N 100005
using namespace std;
set<int> getAbundantSet() {
   set<int> abundant_set;
   for (int i = 1; i < N; i++) {
      int sum = 1;
      for (int j = 2; j * j <= i; j++) {
         if (i % j == 0) {
            sum += j;
            if (i / j != j)
            sum += i / j;
         }
      }
      if (sum > i)
         abundant_set.insert(i);
   }
   return abundant_set;
}
void representSumAbundant(int number){
   set<int> abundant_set = getAbundantSet();
   for (int i = 1; i <= number; i++) {
      if (abundant_set.count(i) && abundant_set.count(number - i)) {
         cout << i << " " << number - i;
         return;
      }
   }
   cout << -1;
}
int main() {
   int n = 30;
   representSumAbundant(n);
}

出力

12 18

この例では n = 30 としています。30 は 12 + 18 と表現でき、12 も 18 も過剰数であるため「12 18」が出力されます。もし該当する組み合わせが存在しなければ、-1 が出力されます。

計算量について

過剰数の集合を構築する処理は O(N√N)、ペアの探索は各判定で set の count（O(log N)）を呼び出すため、全体で O(N log N) 程度の計算量で実行できます。