Pythonで整数が2つの半素数の合計として表現できるかどうかを判定する方法

この記事では、ある整数 n が与えられたとき、それを2つの半素数（セミプライム）の合計として表現できるかどうかをPythonで判定する方法を解説します。

半素数とは？

半素数とは、2つの素数の積として表現できる数のことです。1〜100の範囲に含まれる半素数は次の通りです。

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95

具体例

たとえば入力が n = 108 の場合、出力は True になります。これは、108 = 14 + 94 と表現でき、14（= 2 × 7）も 94（= 2 × 47）もどちらも半素数だからです。

解決手順

この問題を解くために、以下の手順に従います。

• MAX := 10000 … 入力は1〜10000の範囲の半素数の合計であると仮定します。
• nums := 空のリスト … 見つかった半素数を格納します。
• s_prime_flags := サイズMAXの配列 … すべて False で初期化し、各数が半素数かどうかのフラグを保持します。

get_semi_primes() 関数の処理

1. i を2からMAX-1まで順に処理します。
   • count := 0、num := i、j := 2 とします。
   • count < 2 かつ j² ≤ num の間、以下を繰り返します。
     • num が j で割り切れる間、num := num / j とし、count を1ずつ増やします。
     • j を1増やします。
   • 残った num > 1 の場合、count をさらに1増やします。
   • count がちょうど2であれば、i は半素数なので s_prime_flags[i] := True とし、nums の末尾に i を追加します。

メイン処理（solve関数）

1. get_semi_primes() を呼び出して半素数の一覧を作成します。
2. i := 0 とし、nums[i] ≤ n // 2 の間、以下を繰り返します。
   • s_prime_flags[n - nums[i]] が True ならば、n は2つの半素数の合計で表せるので True を返します。
   • i を1増やします。
3. 該当する組み合わせが見つからなければ False を返します。

実装例

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

MAX = 10000
nums = []
s_prime_flags = [False] * MAX

def get_semi_primes():
    for i in range(2, MAX):
        count = 0
        num = i
        j = 2
        while count < 2 and j * j <= num:
            while num % j == 0:
                num /= j
                count += 1
            j += 1
        if num > 1:
            count += 1
        if count == 2:
            s_prime_flags[i] = True
            nums.append(i)

def solve(n):
    get_semi_primes()
    i = 0
    while nums[i] <= n // 2:
        if s_prime_flags[n - nums[i]] == True:
            return True
        i += 1
    return False

n = 108
print(solve(n))

入力

n = 108

出力

True

まとめ

このアルゴリズムでは、まず素因数分解の考え方を用いて各数が半素数かどうかを事前に判定し、その後「n から半素数を引いた値も半素数になるか」を順番に確認することで答えを求めています。計算量は O(MAX × √MAX) 程度で抑えられ、前計算により複数のクエリにも効率的に対応できます。