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


: prime? ( n -- ? ) here + c@ 0= ;
: notprime! ( n -- ) here + 1 swap c! ;
 
: sieve ( n -- )
  here over erase
  0 notprime!
  1 notprime!
  2
  begin
    2dup dup * >
  while
    dup prime? if
      2dup dup * do
        i notprime!
      dup +loop
    then
    1+
  repeat
  2drop ;
 
: left_truncatable_prime? ( n -- flag )
  dup prime? invert if
    drop false exit
  then
  dup >r
  10
  begin
    2dup >
  while
    2dup mod
    dup r> = if
      2drop drop false exit
    then
    dup prime? invert if
      2drop drop false exit
    then
    >r
    10 *
  repeat
  2drop rdrop true ;
 
: right_truncatable_prime? ( n -- flag )
  dup prime? invert if
    drop false exit
  then
  begin
    10 / dup 0 >
  while
    dup prime? invert if
      drop false exit
    then
  repeat
  drop true ;
 
: max_left_truncatable_prime ( n -- )
  begin
    dup 0 >
  while    
    dup left_truncatable_prime? if . cr exit then
    1-
  repeat drop ;
 
: max_right_truncatable_prime ( n -- )
  begin
    dup 0 >
  while    
    dup right_truncatable_prime? if . cr exit then
    1-
  repeat drop ;
 
1000000 constant limit
 
limit 1+ sieve
 
." Largest left truncatable prime: "
limit max_left_truncatable_prime
 
." Largest right truncatable prime: "
limit max_right_truncatable_prime
 
bye