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


#!/usr/local/bin/a68g --script #
 
PROC is prime = (INT n)BOOL:(
  []BOOL is short prime=(FALSE, TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE);
  IF n<=UPB is short prime THEN is short prime[n] # EXIT # ELSE
    IF ( NOT ODD n | TRUE | n MOD 3 = 0 ) THEN FALSE # EXIT # ELSE
      INT h := ENTIER sqrt(n)+3;
      FOR a FROM 7 BY 6 WHILE a<h DO
        IF ( n MOD a = 0 | TRUE |  n MOD (a-2) = 0 ) THEN false exit FI
      OD;
      TRUE # EXIT #
    FI
  FI EXIT
  false exit: FALSE
);
 
PROC string to int = (STRING in a)INT:(
  FILE f; STRING a := in a; associate(f, a);
  INT i; get(f, i); close(f);
  i
);
 
PROC is trunc prime = (INT in n, PROC(REF STRING)VOID trunc)BOOL: (
  INT n := in n;
  STRING s := whole(n, 0);
  IF char in string("0", NIL, s) THEN FALSE # EXIT #
  ELSE
    WHILE is prime(n) DO
      s := whole(n, 0);
      trunc(s);
      IF UPB s = 0 THEN true exit FI;
      n := string to int(s)
    OD;
    FALSE EXIT
    true exit: TRUE
  FI
);
 
PROC get trunc prime = (INT in n, PROC(REF STRING)VOID trunc)VOID:(
  FOR n FROM in n BY -1 TO 1 DO
    IF is trunc prime(n, trunc) THEN
      printf(($g(0)l$, n));
      break
    FI
  OD;
  break: ~
);
 
main:(
  INT limit = 1000000;
  printf(($g g(0) gl$,"Highest left- and right-truncatable primes under ",limit,":"));
  get trunc prime(limit, (REF STRING s)VOID: s := s[LWB s+1:]);
  get trunc prime(limit, (REF STRING s)VOID: s := s[:UPB s-1]);
  write("Press Enter");
  read(newline)
)