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 sets, strutils, algorithm
 
proc primes(n: int64): seq[int64] =
  var multiples: HashSet[int64]
  for i in 2..n:
    if i notin multiples:
      result.add i
      for j in countup(i*i, n, i.int):
        multiples.incl j
 
proc truncatablePrime(n: int64): tuple[left, right: int64] =
  var
    primelist: seq[string]
  for x in primes(n):
    primelist.add($x)
  reverse primelist
  var primeset = primelist.toHashSet
  for n in primelist:
    var alltruncs: HashSet[string]
    for i in 0..n.high:
      alltruncs.incl n[i..n.high]
    if alltruncs <= primeset:
      result.left = parseInt(n)
      break
  for n in primelist:
    var alltruncs: HashSet[string]
    for i in 0..n.high:
      alltruncs.incl n[0..i]
    if alltruncs <= primeset:
      result.right = parseInt(n)
      break
 
echo truncatablePrime(1000000i64)