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


V MAX_PRIME = 1000000
V primes = [1B] * MAX_PRIME
primes[0] = primes[1] = 0B
 
V i = 2
L i * i < MAX_PRIME
   L(j) (i * i .< MAX_PRIME).step(i)
      primes[j] = 0B
   i++
   L i < MAX_PRIME & !primes[i]
      i++
 
F left_trunc(=n)
   V tens = 1
   L tens < n
      tens *= 10
 
   L n != 0
      I !:primes[n]
         R 0B
      tens I/= 10
      I n < tens
         R 0B
      n %= tens
 
   R 1B
 
F right_trunc(=n)
   L n != 0
      I !:primes[n]
         R 0B
      n I/= 10
   R 1B
 
L(n) (MAX_PRIME - 1 .< 0).step(-2)
   I left_trunc(n)
      print(‘Left: ’n)
      L.break
 
L(n) (MAX_PRIME - 1 .< 0).step(-2)
   I right_trunc(n)
      print(‘Right: ’n)
      L.break