64 lines
1.6 KiB
Python
64 lines
1.6 KiB
Python
#!/usr/bin/env python3
|
|
|
|
# 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.
|
|
|
|
from projecteuler import is_prime, timing
|
|
|
|
|
|
def is_tr_prime(n: int) -> bool:
|
|
# One-digit numbers and non-prime numbers are
|
|
# not truncatable primes.
|
|
if n < 11 or not is_prime(n):
|
|
return False
|
|
|
|
tmp = n // 10
|
|
|
|
# Remove one digit at a time from the right and check
|
|
# if the resulting number is prime. Return 0 if it isn't.
|
|
while tmp > 0:
|
|
if not is_prime(tmp):
|
|
return False
|
|
|
|
tmp = tmp // 10
|
|
|
|
# Starting from the last digit, check if it's prime, then add back one digit at a time on the left and check if it
|
|
# is prime. Return 0 when it isn't.
|
|
i = 10
|
|
tmp = n % i
|
|
|
|
while tmp != n:
|
|
if not is_prime(tmp):
|
|
return False
|
|
|
|
i = i * 10
|
|
tmp = n % i
|
|
|
|
# If it gets here, the number is truncatable prime.
|
|
return True
|
|
|
|
|
|
@timing
|
|
def p037() -> None:
|
|
i = 0
|
|
n = 1
|
|
_sum = 0
|
|
|
|
# Check every number until 11 truncatable primes are found.
|
|
while i < 11:
|
|
if is_tr_prime(n):
|
|
_sum = _sum + n
|
|
i = i + 1
|
|
n = n + 1
|
|
|
|
print('Project Euler, Problem 37')
|
|
print(f'Answer: {_sum}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p037()
|