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 Data.Numbers.Primes(primes, isPrime)
import Data.List
import Control.Arrow
 
primes1e6 = reverse. filter (notElem '0'. show) $ takeWhile(<=1000000) primes
 
rightT, leftT :: Int -> Bool
rightT = all isPrime. takeWhile(>0). drop 1. iterate (`div`10)
leftT x = all isPrime. takeWhile(<x).map (x`mod`) $ iterate (*10) 10
 
main = do 
  let (ltp, rtp) = (head. filter leftT &&& head. filter rightT) primes1e6
  putStrLn $ "Left truncatable  " ++ show ltp
  putStrLn $ "Right truncatable " ++ show rtp