Pythonで配列内の素数要素の合計が素数かどうかを判定する方法

問題の概要

配列 nums が与えられたとき、その配列に含まれるすべての素数要素の合計もまた素数になっているかどうかを判定します。

たとえば、入力が nums = [1, 2, 4, 5, 3, 3] の場合を考えてみましょう。この配列に含まれる素数は 2、5、3、3 の4つで、その合計は 2 + 5 + 3 + 3 = 13 です。13 自身も素数であるため、出力は True となります。

解き方のアプローチ

この問題を効率よく解くには、エラトステネスの篩(ふるい)を使ってあらかじめ素数表を作成しておくのが効果的です。素数表があれば、各要素や合計値が素数かどうかを O(1) で即座に判定できます。

アルゴリズムの手順

1. 上限値として MAX = 10000 を定義する
2. サイズ MAX のブール型リスト sieve を作成し、すべて True で初期化する
3. generate_list_of_primes() 関数を定義する
4. sieve[0] と sieve[1] を False に設定する(0 と 1 は素数ではないため)
5. i を 2 から MAX − 1 まで順に処理する:
   • sieve[i] が True(i が素数)の場合、j を i² から MAX まで i 刻みで回しながら sieve[j] を False にする(i の倍数はすべて合成数のため)
6. メイン処理では以下を実行する:
   • generate_list_of_primes() を呼び出して素数表を生成する
   • 合計値 total を 0 で初期化する
   • 配列の各要素を走査し、sieve[要素] が True なら素数なので total に加算する
   • 最後に sieve[total] が True なら True を返し、それ以外は False を返す

実装例

以下が実際のPythonコードです。

MAX = 10000
sieve = [True] * MAX

def generate_list_of_primes():
    sieve[0] = False
    sieve[1] = False

    for i in range(2, MAX):
        if sieve[i]:
            # i の倍数をふるい落とす(i*i から開始すれば十分)
            for j in range(i * i, MAX, i):
                sieve[j] = False

def solve(arr):
    generate_list_of_primes()
    total = 0
    for num in arr:
        if sieve[num]:       # 要素が素数なら加算
            total += num

    return sieve[total]      # 合計が素数かどうかを返す

nums = [1, 2, 4, 5, 3, 3]
print(solve(nums))

入力

[1, 2, 4, 5, 3, 3]

出力

True

ポイントのまとめ

• エラトステネスの篩による素数表の生成は、計算量 O(MAX log log MAX) と非常に高速です。
• 内側のループは i * i から始めるのが定石です。それ未満の倍数は、より小さい素数の段階ですでにふるい落とされているためです。
• この実装では配列の要素と合計値が MAX 未満である必要があります。扱うデータの範囲に応じて MAX の値を調整してください。