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


with javascript_semantics
constant N = 6, limit = power(10,N)
-- standard sieve:
enum L,R  -- (with primes[i] as mini bit-field)
sequence primes = repeat(L+R, limit)
primes[1] = 0
for i=2 to floor(sqrt(limit)) do
    if primes[i] then
        for k=i*i to limit by i do
            primes[k] = 0
        end for
    end if
end for
 
-- propagate non-truncateables up the prime table:
for p=1 to N-1 do
    integer p10 = power(10,p)       -- ie 10, 100, .. 100_000
    for i=p10+1 to p10*10-1 by 2 do -- to 99, 999, .. 999_999
        if primes[i] then
            integer l = remainder(i,p10),
                    r = floor(i/10)
            integer pi = and_bits(primes[l],L)+and_bits(primes[r],R)
            if pi and find('0',sprint(i)) then pi = 0 end if
            primes[i] = pi
        end if
    end for
end for
 
integer maxl=0, maxr=0
 
for i=limit-1 to 1 by -2 do
    integer pi = primes[i]
    if pi then
        if maxl=0 and and_bits(pi,L) then maxl = i end if
        if maxr=0 and and_bits(pi,R) then maxr = i end if
        if maxl!=0 and maxr!=0 then exit end if
    end if
end for
?{maxl,maxr}
