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


FUNCTION isPrime RETURNS LOGICAL (
   i_i AS INT
):
 
   DEF VAR ii AS INT.
 
   DO ii = 2 TO SQRT( i_i ):
 
      IF i_i MODULO ii = 0 THEN
         RETURN FALSE.
 
   END.
 
   RETURN TRUE AND i_i > 1.
 
END FUNCTION. /* isPrime */
 
FUNCTION isLeftTruncatablePrime RETURNS LOGICAL (
   i_i AS INT
):
 
   DEF VAR ii        AS INT.
   DEF VAR cc        AS CHAR.
   DEF VAR lresult   AS LOGICAL INITIAL TRUE.
 
   cc = STRING( i_i ).
 
   DO WHILE cc > "":
      lresult = lresult AND isPrime( INTEGER( cc ) ).
      cc = SUBSTRING( cc, 2 ).
   END.
 
   RETURN lresult.
 
END FUNCTION. /* isLeftTruncatablePrime */
 
FUNCTION isRightTruncatablePrime RETURNS LOGICAL (
   i_i AS INT
):
 
   DEF VAR ii        AS INT.
   DEF VAR cc        AS CHAR.
   DEF VAR lresult   AS LOGICAL INITIAL TRUE.
 
   cc = STRING( i_i ).
 
   DO WHILE cc > "":
      lresult = lresult AND isPrime( INTEGER( cc ) ).
      cc = SUBSTRING( cc, 1, LENGTH( cc ) - 1 ).
   END.
 
   RETURN lresult.
 
END FUNCTION. /* isRightTruncatablePrime */
 
FUNCTION getHighestTruncatablePrimes RETURNS CHARACTER (
   i_imax AS INTEGER
):
 
   DEF VAR ii        AS INT.
   DEF VAR ileft     AS INT.
   DEF VAR iright    AS INT.
 
   DO ii = i_imax TO 1 BY -1 WHILE ileft = 0 OR iright = 0:
 
      IF INDEX( STRING( ii ), "0" ) = 0 THEN DO:
         IF ileft = 0 AND isLeftTruncatablePrime( ii ) THEN
            ileft = ii.
         IF iright = 0 AND isRightTruncatablePrime( ii ) THEN
            iright = ii.
      END.
 
   END.
 
   RETURN SUBSTITUTE("Left: &1~nRight: &2", ileft, iright ).
 
END FUNCTION. /* getHighestTruncatablePrimes */
 
MESSAGE 
   getHighestTruncatablePrimes( 1000000 )
VIEW-AS ALERT-BOX.
 