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


 
tp: procedure options (main);
    declare primes(1000000) bit (1);
    declare max_primes fixed binary (31);
    declare (i, k) fixed binary (31);
 
    max_primes = hbound(primes, 1);
    call sieve;
 
   /* Now search for primes that are right-truncatable. */
   call right_truncatable;
 
   /* Now search for primes that are left-truncatable. */
   call left_truncatable;
 
right_truncatable: procedure;
   declare direction bit (1);
   declare (i, k) fixed binary (31);
 
test_truncatable:
   do i = max_primes to 2 by -1;
      if primes(i) then /* it's a prime */
         do;
            k = i/10;
            do while (k > 0);
               if ^primes(k) then iterate test_truncatable;
               k = k/10;
            end;
            put skip list (i || ' is right-truncatable');
            return;
         end;
   end;
end right_truncatable;
 
left_truncatable: procedure;
   declare direction bit (1);
   declare (i, k, d, e) fixed binary (31);
 
test_truncatable:
   do i = max_primes to 2 by -1;
      if primes(i) then /* it's a prime */
         do;
            k = i;
            do d = 100000 repeat d/10 until (d = 10);
               e = k/d;
               k = k - e*d;
               if e = 0 then iterate test_truncatable;
               if ^primes(k) then iterate test_truncatable;
            end;
            put skip list (i || ' is left-truncatable');
            return;
         end;
   end;
end left_truncatable;
 
sieve: procedure;
   declare (i, j) fixed binary (31);
 
   primes = '1'b; primes(1) = '0'b;
 
   do i = 2 to sqrt(max_primes);
      do j = i+i to max_primes by i;
         primes(j) = '0'b;
      end;
   end;
end sieve;
 
end tp;
 