在 Python 中查找小于 N 的所有可截断素数之和

假设我们有一个给定的整数 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

  • 对于 i 从 2 到 N，执行：

    • 如果 prime[i] 等于 True，则

      • 对于 j 从 i * 2 到 N，每次递增 i，执行：

        • prime[j] := False

  • 从主方法中，执行以下操作：

  • sum := 0

  • 对于 i 从 2 到 n，执行：

    • 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))

输入

55

输出

130

更新于：2020年8月27日

231 次浏览

开启你的职业生涯

完成课程获得认证

开始
广告