Pythonで数値が二面素数（Dihedral Prime）かどうかを判定する方法

ある整数nが与えられたとき、それが「二面素数（dihedral prime）」であるかどうかを判定する方法を解説します。二面素数とは、その数自体が素数であり、さらに7セグメントディスプレイに表示した際に、表示の向き（通常の向きでも上下逆さまでも）に関わらず、同じ数または別の素数として読み取れる数のことです。

例えば、入力がn = 1181の場合、出力はTrueになります。

下の数字は上の数字を上下逆さま（180度回転）にして表示したものであり、どちらも素数となっています。

アルゴリズムの手順

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

• up_side_down() 関数を定義します。引数としてnを受け取ります。
• temp := n、total := 0 と初期化します。
• temp > 0 の間、以下を繰り返します。
  • d := temp mod 10（一の位の数字を取り出す）
  • dが2の場合は d := 5 に置き換える
  • dが5の場合は d := 2 に置き換える
  • total := total * 10 + d
  • temp := temp / 10 の商
• total を返します。
• メイン処理では以下を行います。
• nが素数でない、または up_side_down(n) が素数でない、または n の桁を逆順にした数が素数でない、または up_side_down(n) の桁を逆順にした数が素数でない場合は、False を返します。
• temp := n とし、temp > 0 の間、以下を繰り返します。
  • rem := temp mod 10
  • rem が [3, 4, 6, 7, 9] のいずれかであれば False を返します（これらの数字は180度回転しても正しい数字として表示できないためです）。
  • temp := temp / 10 の商
• すべてのチェックを通過すれば True を返します。

なお、素数判定にはエラトステネスの篩を用いて、あらかじめ10万までの素数テーブルを作成しています。これにより各判定を高速に行うことができます。

実装コード例

prime = (int(1e5)+5)*[True]
def reverse(n):
    return int(str(n)[::-1])

def up_side_down(n):
    temp = n
    total = 0
    while temp>0:
        d = temp % 10
        if d == 2:
            d = 5
        elif d == 5:
            d = 2
        total = total * 10 + d
        temp//= 10

    return total

def get_all_prime():
    prime[0] = prime[1] = False

    for i in range(2, int(1e5)+1):
        j = 2
        while i * j<= int(1e5):
            prime[i * j] = False
            j+= 1

def solve(n):
    get_all_prime()
    if not prime[n] or not prime[up_side_down(n)] or not prime[reverse(n)] or not prime[reverse(up_side_down(n))]:
        return False

    temp = n

    while temp>0:
        rem = temp % 10;
        if rem in [3, 4, 6, 7, 9]:
            return False
        temp //= 10

    return True

n = 1181
print(solve(n))

入力

n = 1181

出力

True

このように、対象の数・上下反転させた数・桁を逆にした数・その両方を組み合わせた数のすべてが素数であり、かつ回転しても正しく表示できる数字（0, 1, 2, 5, 8）のみで構成されている場合、その数は二面素数であると判定できます。