Pythonで数の「より良い」約数を見つける方法

問題の概要

ある数 n が与えられたとき、その約数の中から条件に基づいて「より良い」約数を見つけます。2つの数 p と q を比較する際、それぞれの各位の数字の合計(桁和)が大きい方を「良い」と判断します。桁和が同じ場合は、値が小さい方を良いとみなします。

たとえば入力が n = 180 のとき、出力は 9 になります。180 の約数は [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180] であり、このうち桁和が最大になるのは [9, 18, 36, 45, 90, 180] の6個です。これらはいずれも桁和が 9 で等しいので、その中で最も小さい値である 9 が答えとなります。

解き方のアプローチ

この問題は以下の手順で解くことができます。

• 答えを格納する div を 1、最大桁和を記録する md を 1 で初期化します。
• i を 2 から n まで順に確認します。
  • k に i を代入します。
  • n % i が 0 より大きい場合(i が約数ではない場合)は、次のループへ進みます。
  • 桁和を計算するため、s を 0 で初期化します。
  • k が 0 より大きい間、次の処理を繰り返します。
    • s に k % 10(下一桁の数字)を加算します。
    • k を 10 で整数除算して桁をひとつずらします。
  • s が md より大きければ、md を s に、div を i に更新します。
• すべての確認が終わったら div を返します。

ここで重要なポイントは、i を小さい順に走査し、s > md(厳密な不等号)のときだけ更新する点です。これにより、桁和が同点の約数が複数存在しても、自動的に最も小さい約数が保持される仕組みになっています。

実装例

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

def solve(n):
    div = 1
    md = 1
    for i in range(2, n + 1):
        k = i
        if n % i > 0:
            continue
        s = 0
        while k > 0:
            s += k % 10
            k //= 10
        if s > md:
            md = s
            div = i

    return div

n = 180
print(solve(n))

入力

180

出力

9

計算量と補足

このアルゴリズムは 2 から n までのすべての整数を調べるため、時間計算量は O(n × d)(d は平均的な桁数)程度になります。n が大きくなると処理が遅くなるため、約数を √n までのペアとして列挙する手法に置き換えることで、大幅な高速化が可能です。また、桁和の計算は sum(map(int, str(k))) のように文字列変換を利用すると、より簡潔に記述できます。