PythonでN以下のすべての切り捨て可能な素数の合計を求めます

与えられた整数Nがあると仮定します。 N未満のすべての切り捨て可能素数の合計を見つける必要があります。切り捨て可能素数は左切り捨て可能素数であることがわかっているため（先頭の「左」桁が連続して削除される場合、結果のすべての数値は素数として扱われます）右切り捨て可能素数（最後の「右」桁が連続して削除された場合、結果のすべての数値は素数として扱われます）。 9137、137、37、および7が素数であるため、これは左切り捨て可能素数であるため、切り捨て可能素数の例は9137です。したがって、9137は切り捨て可能な素数です。

したがって、入力がN =55の場合、出力は（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

• メインの方法から、次のようにします-

• 合計：=0

• 2からnの範囲のiの場合、実行します

  • 現在：=i

  • f：=True

• 電流がゼロ以外の場合は、実行してください

  • prime [current]がFalseの場合、

    • f：=False

    • ループから出てきます

  • current：=current / 10

• 現在：=i

• パワー：=10

• （電流/電力）の商がゼロ以外の場合は、

  • prime [current mod power]がFalseの場合、

    • f：=False

    • ループから出てきます

  • パワー：=パワー* 10

• fがTrueの場合、

  • 合計：=合計+ i

• 合計を返す

例

理解を深めるために、次の実装を見てみましょう-

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