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


max_number = 1000000
 
numbers = {}
for i = 2, max_number do
    numbers[i] = i;
end
 
for i = 2, max_number do
    for j = i+1, max_number do
        if numbers[j] ~= 0 and j % i == 0 then numbers[j] = 0 end
    end
end
 
max_prime_left, max_prime_right = 2, 2
for i = 2, max_number do
    if numbers[i] ~= 0 then 
        local is_prime = true
 
        local l = math.floor( i / 10 )
        while l > 1 do
            if numbers[l] == 0 then
                is_prime = false
                break 
            end
            l = math.floor( l / 10 )
        end
        if is_prime then
            max_prime_left = i
        end
 
        is_prime = true
        local n = 10;
        while math.floor( i % 10 ) ~= 0 and n < max_number do
            if numbers[ math.floor( i % 10 ) ] ~= 0 then
                is_prime = false
                break
            end
            n = n * 10
        end    
        if is_prime then
            max_prime_right = i
        end
    end
end
 
print( "max_prime_left = ", max_prime_left )
print( "max_prime_right = ", max_prime_right )