Pythonで素数を掛け合わせて配列の要素をすべて等しくできるか判定する方法

問題の概要

2つの配列が与えられます。1つは整数の配列 nums、もう1つは素数の配列 primes です。nums の各要素に、primes から選んだ1つ以上の素数を掛ける操作を組み合わせることで、すべての要素を同じ値にできるかどうかを判定するのがこの問題の目的です。

たとえば、nums = [25, 100]、primes = [2, 5] の場合、答えは True になります。25 に 2 を2回掛ければ 100 になり、両方の要素が同じ値になるためです。

解法のアプローチ：最小公倍数（LCM）を活用する

この問題は、全要素の最小公倍数（LCM）を基準にすると効率的に解けます。手順は以下の通りです。

• ステップ1： nums の全要素の最小公倍数（LCM）を求める
• ステップ2： 各要素 nums[i] について val = LCM ÷ nums[i] を計算する
• ステップ3： val が素数で割り切れる限り、primes の素数で割り続ける
• ステップ4： 最終的に val が 1 になっていなければ False を返す
• ステップ5： すべての要素で val が 1 になれば True を返す

この方法が正しい理由は、共通の目標値が存在するなら、その値は必ず全要素の倍数、つまり最小公倍数の倍数になるからです。したがって、「各要素から最小公倍数へ到達できるか（その差分が与えられた素数だけの積で構成されるか）」を確認すれば十分です。

Pythonでの実装例

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

from math import gcd

def array_lcm(nums):
    ans = nums[0]
    for i in range(1, len(nums)):
        ans = ans * nums[i] // gcd(nums[i], ans)
    return ans

def solve(nums, primes):
    lcm_arr = array_lcm(nums)
    for i in range(len(nums)):
        val = lcm_arr // nums[i]
        for p in primes:
            while val % p == 0:
                val //= p
        if val != 1:
            return False
    return True

nums = [25, 100]
primes = [2, 5]
print(solve(nums, primes))

入力

[25, 100], [2, 5]

出力

True

処理の流れを確認

この例では、まず LCM(25, 100) = 100 を計算します。

• 要素 25 に対しては val = 100 ÷ 25 = 4 となり、これを素数 2 で2回割ると 1 になります。
• 要素 100 に対しては val = 1 であり、最初から条件を満たしています。

すべての要素で val が 1 になったため、結果は True となります。

計算量について

要素数を n、配列内の最大値を M、素数の個数を k とすると、LCMの計算には O(n log M)、各要素の検証にも高々 O(k log M) 程度しかかかりません。全体として非常に効率的なアルゴリズムであり、大きな入力に対しても実用的に動作します。