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 extensions;
 
const MAXN = 1000000;
 
extension mathOp
{
    isPrime()
    {
        int n := cast int(self);
 
        if (n < 2) { ^ false };        
        if (n < 4) { ^ true };        
        if (n.mod:2 == 0) { ^ false };
        if (n < 9) { ^ true }; 
        if (n.mod:3 == 0) { ^ false };
 
        int r := n.sqrt();
        int f := 5;
        while (f <= r)
        {
            if ((n.mod(f) == 0) || (n.mod(f + 2) == 0))
                { ^ false };
 
            f := f + 6            
        };
 
        ^ true
    }
 
    isRightTruncatable()
    {
        int n := self;
 
        while (n != 0)
        {
            ifnot (n.isPrime())
                { ^ false };
 
            n := n / 10
        };
 
        ^ true
    }
 
    isLeftTruncatable()
    {
        int n := self;
        int tens := 1;
 
        while (tens < n)
            { tens := tens * 10 };
 
        while (n != 0)
        {
            ifnot (n.isPrime())
                { ^ false };
 
            tens := tens / 10;
            n := n - (n / tens * tens)
        };
 
        ^ true
    }
}
 
public program()
{
    var n := MAXN;
    var max_lt := 0;
    var max_rt := 0;
 
    while (max_lt == 0 || max_rt == 0)
    {
        if(n.toString().indexOf("0") == -1)
        {
            if ((max_lt == 0) && (n.isLeftTruncatable()))
                {
                    max_lt := n
                };
 
            if ((max_rt == 0) && (n.isRightTruncatable()))
                {
                    max_rt := n
                }
        };
 
        n := n - 1
    };
 
    console.printLine("Largest truncable left is ",max_lt);   
    console.printLine("Largest truncable right is ",max_rt);
 
    console.readChar()
}