Pythonで素数の配列の積が完全平方数かどうかを判定する方法

すべての要素が素数である配列 nums が与えられたとします。このとき、配列内の全要素の積が完全平方数（平方数）であるかどうかを判定する必要があります。

たとえば、入力が nums = [3,3,7,7] の場合、出力は True になります。すべての要素の積は 441 となり、21² = 441 であるため、441 は完全平方数だからです。

解法のアプローチ

この問題は、素因数分解の性質を使うことで効率的に解けます。ある数が完全平方数であるためには、その素因数の指数がすべて偶数でなければなりません。つまり、配列内の各素数の出現回数を数え、1つでも奇数回現れる素数が存在すれば、その積は完全平方数にはなりません。

手順は以下の通りです。

• m := 配列 nums 内の各要素とその出現頻度を保持するマップ（辞書）を作成します。
• nums の各キーについて次を繰り返します。
  • m[key] が奇数であれば False を返します。
• すべてのキーが偶数回出現していれば True を返します。

この方法では、実際に大きな積を計算する必要がないため、桁あふれや多倍長整数演算のコストを避けられます。計算量は時間・空間ともに O(n) と効率的です。

実装例

以下の実装を見ると、より理解しやすくなります。

from collections import defaultdict
def solve(nums) :
    m = defaultdict(int)
    for key in nums :
        m[key] += 1
    for key in nums :
        if m[key] % 2 == 1 :
            return False
    return True

nums = [3,3,7,7]
print(solve(nums))

入力

[3,3,7,7]

出力

True