在 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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始
廣告