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.]


bool is_trunc_prime(int p, string direction)
{
    while(p) {
	if( !p->probably_prime_p() )
	    return false;
	if(direction == "l")
	    p = (int)p->digits()[1..];
	else
	    p = (int)p->digits()[..<1];
    }
    return true;
}
 
void main()
{
    bool ltp_found, rtp_found;
    for(int prime = 10->pow(6); prime--; prime > 0) {
	if( !ltp_found && is_trunc_prime(prime, "l") ) {
	    ltp_found = true;
	    write("Largest LTP: %d\n", prime);
	}
	if( !rtp_found && is_trunc_prime(prime, "r") ) {
	    rtp_found = true;
	    write("Largest RTP: %d\n", prime);
	}
	if(ltp_found && rtp_found)
	    break;
    }
}