Project Euler 37

Question: 

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

문제:

3797은 흥미로운 성질이 있다. 그 수 자체도 소수이지만, 왼쪽에서 오른쪽으로 한 자리씩 지워나가도 계속해서 소수가 되고(3797, 797, 97, 7 모두 소수이다.) 오른쪽에서 왼쪽으로 한 자리씩 지워나가도 계속해서 소수가 된다.(3797, 379, 37, 3 모두 소수이다.)

이러한 흥미로운 성질이 있는 11개의 소수를 찾아 그 합을 구하여라.

주의: 2, 3, 5, 7은 아니다.

Solution:

from sympy import isprime, sieve
import time
truncatable = list()

def truncPrime(n):
    numlist = list(str(n))
    if len(numlist) >= 3:  # 짝수를 포함하는 경우를 제외
        if numlist.count('0') != 0:
            return False
        elif numlist.count('2') != 0:
            return False
        elif numlist.count('4') != 0:
            return False
        elif numlist.count('6') != 0:
            return False
        elif numlist.count('8') != 0:
            return False
    
    for i in range(len(str(n))):
        if not isprime(int("".join(numlist))):
            return False
        numlist.pop(0) #첫 자리수를 지운다

    numlist = list(str(n))
    for i in range(len(str(n))):
        if not isprime(int("".join(numlist))):
            return False
        numlist.pop(-1) # 마지막 자리수를 지운다.
    return True

i = 8 # starting from known truncatable prime 23
start = time.time()
while len(truncatable) < 11:
    sieve.extend_to_no(i)
    num = sieve._list[i - 1]
    if truncPrime(num) == True:
        truncatable.append(num)
    i += 1

print("""Sum of 11 truncatable primes: {}
List: {}
Found in ...{:.2f}s""".format(sum(truncatable),truncatable,time.time() - start))

Output:

List: [23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]

Found in ...0.26s

748317