Pythonで数Nが強素数（ストロングプライム）かどうかを判定する方法

強素数とは？

ある数 n が与えられたとき、それが強素数（strong prime）であるかどうかを判定します。強素数とは、「直前の素数」と「直後の素数」の平均値よりも大きい素数のことです。

例えば、num = 37 の場合、出力は True になります。これは、37 に最も近い素数が 31 と 41 であり、その平均は (31 + 41) / 2 = 36。37 は 36 より大きいため、強素数と判断されるからです。

ちなみに、2 を除外しているのは、2 より小さい素数が存在しないため平均値が計算できないからです。

アルゴリズムの手順

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

• num が素数でない場合、または num が 2 の場合は False を返す
• last := num − 1、next := num + 1 と初期化する
• next が素数になるまで、next を 1 ずつ増やしていく
• last が素数になるまで、last を 1 ずつ減らしていく
• avg := (last + next) / 2 を計算する
• num > avg であれば True を返す
• それ以外は False を返す

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def solve(num):
    if isPrime(num) == False or num == 2:
        return False
    last = num - 1
    next = num + 1
    while isPrime(next) == False:
        next += 1
    while isPrime(last) == False:
        last -= 1
    avg = (last + next) / 2
    if num > avg:
        return True
    return False

num = 37
print(solve(num))

入力

37

出力

True

補足：効率化のポイント

上記の isPrime 関数はシンプルですが、2 から num−1 まで全て確認するため大きな数では非効率です。実際には、√num までの約数をチェックすれば十分なので、range(2, int(num**0.5) + 1) とすることで計算量を大幅に削減できます。

また、強素数は暗号学の分野でも重要な概念です。特に RSA 暗号の鍵生成において、強素数を使うことでポラード・ロー法などの因数分解アルゴリズムに対する耐性が高まるとされています。