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.
Here's my implementation in Python, it's very slow(takes like 10 secs to show results. How to make it faster, more efficient?
def is_prime(number):
"""returns True for a prime number, False otherwise."""
if number == 1:
return False
factor = 2
while factor * factor <= number:
if number % factor == 0:
return False
factor += 1
return True
def get_truncatable(n):
"""returns truncatable numbers within range n."""
for number in range(9, n, 2):
if is_prime(number):
check = 0
for index in range(-1, -len(str(number)), -1):
less_right = str(number)[:index]
if not is_prime(int(less_right)):
check += 1
if check == 0:
for index in range(1, len(str(number))):
less_left = str(number)[index:]
if not is_prime(int(less_left)):
check += 1
if check == 0:
yield number
if __name__ == '__main__':
print(sum(list(get_truncatable(1000000))))