C++で約数がちょうど4個の整数の約数の総和を求める方法

整数配列 nums が与えられたとき、その中から「約数がちょうど4個」である整数を見つけ出し、それらの約数の総和を計算する問題を考えてみましょう。もし該当する整数が配列内に1つも存在しない場合は、0 を返します。

例えば、入力が [21, 4, 7] の場合、出力は 32 になります。これは次のような理由によるものです。

• 21 の約数は 1, 3, 7, 21 の4つ → 条件を満たす
• 4 の約数は 1, 2, 4 の3つ → 条件を満たさない
• 7 の約数は 1, 7 の2つ → 条件を満たさない

したがって、答えは条件を満たす 21 の約数の総和である 32 となります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• ok() というメソッドを定義します。引数として整数 x を受け取ります
• ret := 1 + x、cnt := 2 と初期化します(1 と x 自身は必ず約数になるため)
• i := 2 から始めて、i² ≤ x である間、i を1ずつ増やしながらループします
  • x が i で割り切れる場合
    • ret に i を加算し、cnt を1増やします
    • i と x/i が異なる場合(つまり平方数ではない場合)は、cnt をさらに1増やし、ret に x/i を加算します
• ループ終了後、cnt が 4 であれば ret を返し、そうでなければ 0 を返します
• メインメソッドでは以下の処理を行います
• ret := 0、n := nums のサイズ とします
• i を 0 から n − 1 までループし、各要素に対して ok(nums[i]) を呼び出して ret に加算していきます
• 最後に ret を返します

この手法では、各整数について √x まで試し割りを行うことで、約数をペアごとに効率よく列挙できます。計算量は配列の長さを n、各要素の最大値を m とすると O(n√m) となり、非常に効率的です。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int ok(int x){
        int ret = 1 + x;
        int cnt = 2;
        for(int i = 2; i * i <= x; i++){
            if(x % i == 0){
                ret += (i);
                cnt++;
                if(i != x / i){
                    cnt++;
                    ret += (x / i);
                }
            }
        }
        return cnt == 4 ? ret : 0;
    }
    int sumFourDivisors(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            ret += ok(nums[i]);
        }
        return ret;
    }
};
main(){
    vector<int> v = {21,4,7};
    Solution ob;
    cout << (ob.sumFourDivisors(v));
}

入力

[21,4,7]

出力

32