C++でnの約数のうち桁和が最大となる値を求めるアルゴリズム

この記事では、整数 n が与えられたときに、n のすべての約数の中で桁の合計(桁和)が最大となる値を求める問題を解説します。基本的な O(n) の解法から、√n を活用した効率的な O(√n) の解法まで、C++ のサンプルコードとともに見ていきましょう。

問題の概要

与えられた整数 n の約数をすべて列挙し、それぞれの桁和を計算します。そして、その中で最も大きな桁和を答えとして返すのが目的です。

入出力例

• 入力: 18
• 出力: 9

解説:

18 の約数は 1, 2, 3, 6, 9, 18 です。それぞれの桁和を計算すると、1, 2, 3, 6, 9, 9 となり、最大値は 9 であることがわかります。

解法アプローチ

基本的な考え方は非常にシンプルで、次の手順で処理を行います。

1. 数 N の約数をすべて求める
2. 各約数について桁和を計算する
3. 桁和が最大となる値を返す

桁和の計算方法

ある整数の桁和は、「10 で割った余りを合計に加算し、その後 10 で整数除算する」という操作を、数値が 0 になるまで繰り返すことで求められます。

基本解法の実装例

まずは、1 から n までのすべての数を順番に調べて約数を見つける、素直な実装です。

#include <iostream>
using namespace std;

// 桁和を計算する関数
int calcDigitSum(int n) {
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

// 最大の桁和を持つ約数の桁和を返す関数
int largestDigitSumDivisor(int n) {
    int maxSum = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0)
            maxSum = max(maxSum, calcDigitSum(i));
    }
    return maxSum;
}

int main() {
    int n = 45;
    cout << "最大の桁和を持つ約数の桁和は " << largestDigitSumDivisor(n) << endl;
    return 0;
}

出力結果

最大の桁和を持つ約数の桁和は 9

45 の約数は 1, 3, 5, 9, 15, 45 であり、桁和はそれぞれ 1, 3, 5, 9, 6, 9 です。したがって最大値は 9 となり、正しく動作していることが確認できます。

計算量を改善する O(√n) アプローチ

上記の方法では 1 から n まで順に確認するため、時間計算量は O(n) になります。ここで、約数はペアで現れるという性質を利用すると、大幅な高速化が可能です。

i が n の約数であれば、n / i も必ず n の約数になります。この性質により、1 から √n までの範囲だけループすれば、すべての約数を網羅的に調べられます。これにより、約数探索の時間計算量は O(√n) に削減されます。

高速化版の実装例

#include <iostream>
using namespace std;

// 桁和を計算する関数
int calcDigitSum(int n) {
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

// √n までループして約数ペアを両方チェックする
int largestDigitSumDivisor(int n) {
    int maxSum = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            maxSum = max(maxSum, calcDigitSum(i));
            maxSum = max(maxSum, calcDigitSum(n / i));
        }
    }
    return maxSum;
}

int main() {
    int n = 32;
    cout << "最大の桁和を持つ約数の桁和は " << largestDigitSumDivisor(n) << endl;
    return 0;
}

出力結果

最大の桁和を持つ約数の桁和は 8

32 の約数は 1, 2, 4, 8, 16, 32 であり、桁和はそれぞれ 1, 2, 4, 8, 7, 5 です。最大値は 8 となり、期待どおりの結果が得られています。

まとめ

本記事では、n の約数の中から桁和が最大となる値を求める問題を取り上げました。ポイントは以下の 2 点です。

• 桁和は「10 での剰余と整数除算の繰り返し」で簡単に計算できる
• 約数は i と n/i のペアで現れるため、√n までのループで全約数を列挙でき、計算量を O(n) から O(√n) に削減できる

n が大きい場合でも高速に動作するため、競技プログラミングや実務においても有用なテクニックです。ぜひ自分のコードにも取り入れてみてください。