Problem 037

Project Euler

Truncatable primes

Problem 37

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.

Since there are only eleven solution, a counter will be use to stop the execution once the program found all the solutions. However, having a list of prime to check against the value would be very helpful, the program will start using an arbitrary list of prime under 1 million and add to it if needed.

This problem is very similar to the problem from problem 35 where the prime in question must not include any even digit or it will never pass the test. Therefore, starting with a list of prime and check if any digit is even, then check both left and right truncatability, stop when eleven solution is found and add them for the final result.