PythonでN未満の切り詰め可能素数（Truncatable Prime）の合計を求める方法

整数 N が与えられたとき、N 未満に存在するすべての切り詰め可能素数（Truncatable Prime）の合計を求める問題を考えてみましょう。

切り詰め可能素数とは？

切り詰め可能素数とは、次の2つの性質をどちらも満たす数のことです。

• 左切り詰め可能素数：先頭（左）の桁を1つずつ取り除いていったとき、現れるすべての数が素数である
• 右切り詰め可能素数：末尾（右）の桁を1つずつ取り除いていったとき、現れるすべての数が素数である

たとえば 9137 を見てみましょう。先頭の桁を順に取り除くと 9137 → 137 → 37 → 7 となり、これらはすべて素数です。このように桁を削っても素数であり続ける数が、切り詰め可能素数として扱われます。

入力と出力の例

入力が N = 55 の場合、出力は 130 になります。これは、55 未満の切り詰め可能素数が 2, 3, 5, 7, 23, 37, 53 の7個であり、その合計が (2 + 3 + 5 + 7 + 23 + 37 + 53) = 130 となるためです。

解法のアプローチ

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

1. ふるい（Sieve）用のサイズとして N := 1000005 を設定する
2. サイズ N の真偽値リスト prime を作成し、すべて True で初期化する
3. sieve() 関数を定義し、エラトステネスの篩によって素数表を作成する
   （prime[0] と prime[1] は False に設定し、i が素数ならば i の倍数をすべて False にしていく）
4. メイン処理では、合計 sum を 0 で初期化し、2 から n-1 までの各数 i について判定を行う
5. 右からの判定：current を i とし、10 で割りながら下の桁を順に取り除き、現れるすべての数が素数か確認する
6. 左からの判定：power を 10 として増やしながら current mod power を求め、先頭側の桁を取り除いた数がすべて素数か確認する
7. 両方の判定を通過した場合のみ、sum に i を加算する
8. 最後に sum を返す

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

N = 1000005
prime = [True for i in range(N)]

def sieve():
    prime[0] = False
    prime[1] = False
    for i in range(2, N):
        if (prime[i] == True):
            for j in range(i * 2, N, i):
                prime[j] = False

def get_total_of_trunc_primes(n):
    total = 0
    for i in range(2, n):
        # 右から桁を取り除いて判定
        current = i
        f = True
        while (current):
            if (prime[current] == False):
                f = False
                break
            current //= 10
        # 左から桁を取り除いて判定
        current = i
        power = 10
        while (current // power):
            if (prime[current % power] == False):
                f = False
                break
            power *= 10
        if f:
            total += i
    return total

n = 55
sieve()
print(get_total_of_trunc_primes(n))

入力

55

出力

130

まとめ

この実装では、あらかじめエラトステネスの篩で素数表を作成しておくことで、各数の判定を O(1) の参照だけで行えるようにしています。桁を取り除く操作は整数の除算（//10）と剰余演算（% power）で実現できるため、文字列変換を一切使わずに効率的に処理できます。結果として、N = 55 のとき 130 という正しい合計が得られました。