Tìm tổng của tất cả các số nguyên tố có thể cắt ngắn dưới N bằng Python

Giả sử chúng ta có một số nguyên N cho trước; chúng ta phải tìm tổng của tất cả các số nguyên tố có thể rút gọn nhỏ hơn N. Như chúng ta biết số nguyên tố có thể cắt ngắn là một số là số nguyên tố có thể cắt bỏ bên trái (nếu chữ số đứng đầu "bên trái" bị loại bỏ liên tiếp, thì tất cả các số kết quả được coi là số nguyên tố) cũng như số nguyên tố có thể cắt ngắn bên phải (nếu chữ số "bên phải" cuối cùng bị xóa liên tiếp, thì tất cả các số kết quả được coi là số nguyên tố). Một ví dụ về số nguyên tố có thể cắt ngắn là 9137 vì đây là số nguyên tố có thể cắt rời vì 9137, 137, 37 và 7 là các số nguyên tố. Do đó, 9137 là một số nguyên tố có thể cắt ngắn.

Vì vậy, nếu đầu vào là N =55, thì đầu ra sẽ là 130 là (2 + 3 + 5 + 7 + 23 + 37 + 53) =

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• N:=1000005

• prime:=một danh sách có kích thước N và điền bằng True

• Xác định một hàm sàng (). Điều này sẽ mất

• số nguyên tố [1]:=Sai, số nguyên tố [0]:=Sai

• đối với tôi trong phạm vi từ 2 đến N, hãy thực hiện

  • nếu số nguyên tố [i] giống với True, thì

    • cho j trong phạm vi i * 2 đến N, cập nhật từng bước theo i, thực hiện

      • prime [j]:=False

• Từ phương thức chính, thực hiện như sau -

• tổng:=0

• đối với tôi trong phạm vi từ 2 đến n, hãy làm

  • hiện tại:=i

  • f:=Đúng

• trong khi hiện tại là khác 0, thực hiện

  • nếu số nguyên tố [hiện tại] là Sai, thì

    • f:=Sai

    • đi ra từ vòng lặp

  • current:=current / 10

• hiện tại:=i

• quyền lực:=10

• trong khi thương số của (hiện tại / công suất) là khác 0, thực hiện

  • nếu nguyên tố [công suất mod hiện tại] là Sai, thì

    • f:=Sai

    • đi ra từ vòng lặp

  • power:=power * 10

• nếu f là True thì

  • sum:=sum + i

• trả lại số tiền

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

55

Đầu ra

130