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


 
function isltruncprime{T<:Integer}(n::T, base::T=10)
    isprime(n) || return false
    p = n
    f = prevpow(base, p)
    while 1 < f
        (d, p) = divrem(p, f)
        isprime(p) || return false
        d != 0 || return false
        f = div(f, base)
    end
    return true
end
 
function isrtruncprime{T<:Integer}(n::T, base::T=10)
    isprime(n) || return false
    p = n
    while base < p
        p = div(p, base)
        isprime(p) || return false
    end
    return true
end
 
hi = 10^6
 
for i in reverse(primes(hi))
    isltruncprime(i) || continue
    println("The largest  left truncatable prime ≤ ", hi, " is ", i, ".")
    break
end
 
for i in reverse(primes(hi))
    isrtruncprime(i) || continue
    println("The largest right truncatable prime ≤ ", hi, " is ", i, ".")
    break
end
 