Pythonで2つの数の積が持つ「約数の最大個数」を求める方法

本記事では、整数型の要素からなる配列が与えられたときに、配列内の2つの数を掛け合わせた積の中から、約数（因子）の個数が最も多いものを見つける方法を解説します。手順はシンプルで、まず配列内の数同士の組み合わせごとの積をすべて計算し、次にそれぞれの積について約数の個数を数え、その中で最大のものを求めます。

入力例と出力例

例1

arr = [3, 2, 10]

出力：

2つの数によって形成される約数の最大個数: 8

• まず組み合わせごとの積を計算します：3 × 2 = 6、3 × 10 = 30、2 × 10 = 20
• 次に、それぞれの値の約数を列挙します：
  6 → 1, 2, 3, 6 ／ 30 → 1, 2, 3, 5, 6, 10, 15, 30 ／ 20 → 1, 2, 4, 5, 10, 20
• 約数の個数を比較すると、6は4個、20は6個、30は8個です。したがって、答えは8となります。

例2

arr = [1, 4, 6]

出力：

2つの数によって形成される約数の最大個数: 8

• 組み合わせごとの積：1 × 4 = 4、1 × 6 = 6、4 × 6 = 24
• 各値の約数：
  4 → 1, 2, 4 ／ 6 → 1, 2, 3, 6 ／ 24 → 1, 2, 3, 4, 6, 8, 12, 24
• 約数の個数は、4が3個、6が4個、24が8個。よって答えは8です。

アルゴリズムの考え方

1. 整数要素を配列に入力します。
2. 積を一時的に保存する変数 product と、約数の最大個数を保存する変数 big を用意します。
3. 外側のループでインデックス i を 0 から配列の長さまで回します。
4. 内側のループでインデックス j を i + 1 から配列の長さまで回します（同じ要素同士や重複した組み合わせを避けるため）。
5. product = arr[i] * arr[j] を計算し、big < count_factor(product) であれば big を更新します。
6. count_factor 関数では、1 からその数自身まで順番に割り切れるかを調べ、割り切れるたびにカウントを1増やして、最終的なカウントを返します。
7. すべての組み合わせを確認した後、big の値を出力します。

Pythonでの実装例

def count_factor(n):
    """n の約数の個数を返す関数"""
    count = 0
    for j in range(1, n + 1):
        if n % j == 0:
            count += 1
    return count

def max_factors(arr):
    """配列内の2つの数の積のうち、約数の個数が最大の値を返す"""
    big = 0
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            product = arr[i] * arr[j]
            big = max(big, count_factor(product))
    return big

if __name__ == "__main__":
    a = [3, 2, 10]
    print("2つの数によって形成される約数の最大個数:", max_factors(a))

出力

2つの数によって形成される約数の最大個数: 8

計算量と高速化のポイント

上記の count_factor は 1 から n まで順に確認するため、1回あたりの計算量は O(n) です。配列の要素数が多く、かつ積の値が大きくなる場合は、平方根まで調べる方法で約数の個数を効率よく求められます。

import math

def count_factor_fast(n):
    """√n まで調べて約数の個数を求める高速版"""
    count = 0
    root = math.isqrt(n)
    for j in range(1, root + 1):
        if n % j == 0:
            # j と n//j がペアの約数。同じ値の場合は1つだけカウント
            count += 1 if j == n // j else 2
    return count

この方法なら計算量が O(√n) に改善され、大きな数でも高速に約数の個数を数えられます。実務では、この高速版の関数を max_factors 内で呼び出すだけでOKです。

まとめ

配列内の2つの数の積に対して約数の個数を比較する問題は、「二重ループによる全探索」と「約数カウント関数」の組み合わせで解決できます。まずはシンプルな実装でロジックを理解し、必要に応じて O(√n) の高速化を適用すると、より大規模なデータにも対応できるコードになります。