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


#MaxLim = 999999
 
Procedure is_Prime(n)
  If     n<=1 : ProcedureReturn #False
  ElseIf n<4  : ProcedureReturn #True
  ElseIf n%2=0: ProcedureReturn #False
  ElseIf n<9  : ProcedureReturn #True
  ElseIf n%3=0: ProcedureReturn #False
  Else
    Protected r=Round(Sqr(n),#PB_Round_Down)
    Protected f=5
    While f<=r
      If n%f=0 Or n%(f+2)=0
        ProcedureReturn #False
      EndIf
      f+6
    Wend
  EndIf
  ProcedureReturn #True
EndProcedure
 
Procedure TruncateLeft(n)
  Protected s.s=Str(n), l=Len(s)-1
  If Not FindString(s,"0",1)
    While l>0
      s=Right(s,l)
      If Not is_Prime(Val(s))
        ProcedureReturn #False
      EndIf
      l-1
    Wend
    ProcedureReturn #True
  EndIf
EndProcedure
 
Procedure TruncateRight(a)
  Repeat
    a/10
    If Not a
      Break
    ElseIf Not is_Prime(a) Or a%10=0
      ProcedureReturn #False
    EndIf
  ForEver
  ProcedureReturn #True
EndProcedure 
 
i=#MaxLim
Repeat
  If is_Prime(i)
    If Not truncateleft And TruncateLeft(i)
      truncateleft=i
    EndIf
    If Not truncateright And TruncateRight(i)
      truncateright=i
    EndIf
  EndIf
  If truncateleft And truncateright
    Break 
  Else
    i-2
  EndIf 
Until i<=0
 
x.s="Largest TruncateLeft= "+Str(truncateleft)
y.s="Largest TruncateRight= "+Str(truncateright)
 
MessageRequester("Truncatable primes",x+#CRLF$+y)