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


object TruncatablePrimes {
  def main(args: Array[String]): Unit = {
    val max = 1000000
 
    println(
      s"""|ltPrime: ${ltPrimes.takeWhile(_ <= max).last}
          |rtPrime: ${rtPrimes.takeWhile(_ <= max).last}
          |""".stripMargin)
  }
 
  def ltPrimes: LazyList[Int] = 2 #:: LazyList.from(3, 2).filter(isLeftTruncPrime)
  def rtPrimes: LazyList[Int] = 2 #:: LazyList.from(3, 2).filter(isRightTruncPrime)
 
  def isPrime(num: Int): Boolean = (num > 1) && !LazyList.range(3, math.sqrt(num).toInt + 1, 2).exists(num%_ == 0)
  def isLeftTruncPrime(num: Int): Boolean = !num.toString.contains('0') && Iterator.unfold(num.toString){str => if(str.nonEmpty) Some((str.toInt, str.tail)) else None}.forall(isPrime)
  def isRightTruncPrime(num: Int): Boolean = !num.toString.exists(_.asDigit%2 == 0) && Iterator.unfold(num.toString){str => if(str.nonEmpty) Some((str.toInt, str.init)) else None}.forall(isPrime)
}