A truncatable prime is a prime number that when you successively remove digits from one end of the prime, you are left with a new prime number.



Examples

The number 997 is called a left-truncatable prime as the numbers 997, 97, and 7 are all prime.

The number 7393 is a right-truncatable prime as the numbers 7393, 739, 73, and 7 formed by removing digits from its right are also prime.

No zeroes are allowed in truncatable primes.



Task

The task is to find the largest left-truncatable and right-truncatable primes less than one million (base 10 is implied).



Related tasks
 
 Find largest left truncatable prime in a given base
 Sieve of Eratosthenes


See also

 Truncatable Prime from MathWorld.]


import std.stdio, std.math, std.string, std.conv, std.algorithm,
       std.range;
 
bool isPrime(in int n) pure nothrow {
    if (n <= 1)
        return false;
    foreach (immutable i; 2 .. cast(int)sqrt(real(n)) + 1)
        if (!(n % i))
            return false;
    return true;
}
 
bool isTruncatablePrime(bool left)(in int n) pure {
    immutable s = n.text;
    if (s.canFind('0'))
        return false;
    foreach (immutable i; 0 .. s.length)
        static if (left) {
            if (!s[i .. $].to!int.isPrime)
                return false;
        } else {
            if (!s[0 .. i + 1].to!int.isPrime)
                return false;
        }
    return true;
}
 
void main() {
    enum n = 1_000_000;
    writeln("Largest left-truncatable prime in 2 .. ", n, ": ",
            iota(n, 1, -1).filter!(isTruncatablePrime!true).front);
    writeln("Largest right-truncatable prime in 2 .. ", n, ": ",
            iota(n, 1, -1).filter!(isTruncatablePrime!false).front);
}