Project Euler 37

• 問題

Problem 37：Truncatable primes
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.

• 解答例

def isPrime(num):
    if num <= 1:
        return False
    elif num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    if not(num % 6 == 1) and not(num % 6 == 5):
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

ans = []
num = 21
while True:
    if not isPrime(num):
        num += 1
        continue
    # check left side
    tempLeft = num
    isLeftPrime = True
    temp = list(str(tempLeft))
    l = len(temp)
    for i in range(l - 1):
        temp.pop(0)
        tempNum = int("".join(temp))
        if not isPrime(tempNum):
            isLeftPrime = False
            break
    if not isLeftPrime:
        num += 1
        continue
    # check right side
    tempRight = num
    isRightPrime = True
    temp = list(str(tempRight))
    l = len(temp)
    for i in range(l - 1):
        temp.pop()
        tempNum = int("".join(temp))
        if not isPrime(tempNum):
            isRightPrime = False
            break
    if not isRightPrime:
        num += 1
        continue

    ans.append(num)
    num += 1

    if len(ans) == 11:
        break

print(sum(ans))