Python에서 N 아래의 모든 절단 가능한 소수의 합 찾기

<시간/>

주어진 정수 N이 있다고 가정합니다. N보다 작은 모든 절단 가능한 소수의 합을 찾아야 합니다. 절단 가능한 소수는 왼쪽 절단 가능한 소수라는 것을 알고 있습니다(앞에 있는 "왼쪽" 숫자가 연속적으로 제거되면 모든 결과 숫자는 소수로 처리됩니다) 오른쪽 절단 가능한 소수(마지막 "오른쪽" 숫자가 연속적으로 제거되면 모든 결과 숫자가 소수로 처리됨). 9137, 137, 37 및 7이 소수이기 때문에 9137은 자를 수 있는 소수의 예입니다. 따라서 9137은 자를 수 있는 소수입니다.

따라서 입력이 N =55와 같으면 출력은 (2 + 3 + 5 + 7 + 23 + 37 + 53) =

와 같이 130이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

N :=1000005
프라임 :=크기 N의 목록과 True로 채우기
sieve() 함수를 정의합니다. 시간이 걸립니다
소수[1] :=거짓, 소수[0] :=거짓
범위 2에서 N까지의 i에 대해 수행
- 프라임[i]이 True와 같으면
  - 범위 i * 2에서 N까지의 j에 대해 i만큼 각 단계에서 업데이트합니다.
    - 소수[j] :=거짓
기본 방법에서 다음을 수행하십시오 -
합계 :=0
범위 2에서 n에 있는 i에 대해 수행
- 현재 :=나는
- f :=참
전류가 0이 아닌 동안 수행
- Prime[current]가 False이면
  - f :=거짓
  - 루프에서 나오다
- 현재 :=현재 / 10
현재 :=나는
전력 :=10
(전류/전력)의 몫이 0이 아닌 동안 수행
- 프라임[현재 모드 전력]이 False이면
  - f :=거짓
  - 루프에서 나오다
- 전력 :=전력 * 10
f가 참이면
- 합계 :=합계 + 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))