在 Python 中查找 N 以下所有可截断素数的总和

pythonserver side programmingprogramming更新于 2025/10/16 1:16:17

假设我们有一个给定的整数 N；我们必须查找小于 N 的所有可截断素数的总和。众所周知，可截断素数是一个左可截断素数(如果连续删除前导"左"数字，则所有结果数字都被视为素数)以及右可截断素数(如果连续删除最后一个"右"数字，则所有结果数字都被视为素数)。可截断素数的一个例子是 9137，因为它是左可截断素数，因为 9137、137、37 和 7 都是素数。因此 9137 是一个可截断素数。

因此，如果输入为 N = 55，则输出将为 130，因为 (2 + 3 + 5 + 7 + 23 + 37 + 53) =

为了解决这个问题，我们将遵循以下步骤 −

N := 1000005
prime := 大小为 N 的列表并用 True 填充
定义一个函数 sieve() 。这将需要
prime[1] := False, prime[0] := False
对于范围为 2 到 N 的 i，执行
- 如果 prime[i] 与 True 相同，则
  - 对于范围为 i * 2 到 N 的 j，在每个步骤中更新 i，执行
    - prime[j] := False
从主方法中，执行以下操作 −
sum := 0
对于范围为 2 到 n 的 i，执行
- current := i
- f := True
当 current 非零时，执行
- 如果 prime[current] 为 False，则
  - f := False
  - 退出循环
- current := current / 10
current := i
power := 10
当 (current / power) 的商非零时，执行
- 如果 prime[current mod power] 为 False，则
  - f := False
  - 退出循环
- power := power * 10
如果 f 为 True，则
- sum := sum + i
返回 sum

示例

让我们看看下面的实现以便更好地理解 −

N = 1000005
prime = [True for i in range(N)]
def sieve():
   prime[1] = False
   prime[0] = 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):
   sum = 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:
      sum += i
   return sum
n = 55
sieve()
print(get_total_of_trunc_primes(n))