Pythonで配列にある整数の約数がすべて含まれているか確認する方法

問題概要

ある配列 nums が与えられたとき、この配列が「ある整数の約数」をすべて含んでいるかどうかを判定します。

たとえば、入力が nums = [1, 2, 3, 4, 6, 8, 12, 24] の場合、これらはすべて 24 の約数であるため、出力は True になります。

解法のアプローチ

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

1. 配列内の最大値を求めます。ある整数の約数リストには必ずその整数自身が含まれるため、配列が完全な約数リストなら、最大値が対象の整数になります。
2. 1 から最大値の平方根まで順に調べ、割り切れる数 i を見つけたら、i と商 maximum // i を一時リストに追加します。i と商が等しい場合(平方数の場合)は、重複を避けるために商の追加をスキップします。
3. 一時リストのサイズが元の配列のサイズと異なる場合は False を返します。
4. 両方のリストをソートし、先頭から順に要素を比較します。一致しない要素があれば False を返します。
5. すべての要素が一致すれば True を返します。

それでは、実際の実装を見てみましょう。

サンプルコード

from math import sqrt

def solve(nums):
    maximum = max(nums)

    temp = []
    for i in range(1, int(sqrt(maximum)) + 1):
        if maximum % i == 0:
            temp.append(i)
            if (maximum // i != i):
                temp.append(maximum // i)

    if len(temp) != len(nums):
        return False

    nums.sort()
    temp.sort()

    for i in range(len(nums)):
        if temp[i] != nums[i]:
            return False
    return True

nums = [1, 2, 3, 4, 6, 8, 12, 24]
print(solve(nums))

入力

[1, 2, 3, 4, 6, 8, 12, 24]

出力

True

計算量のポイント

約数の列挙は最大値 N の平方根まで調べればよいため O(√N)、ソートには O(k log k)(k は配列の長さ)が必要です。全体の計算量は O(√N + k log k) となり、1 から N まで順番にすべて試す素朴な方法 O(N) よりも大幅に効率的です。