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


module primes_mod
  implicit none
 
  logical, allocatable :: primes(:)
 
contains
 
subroutine Genprimes(parr)
  logical, intent(in out) :: parr(:)
  integer :: i
! Prime sieve
  parr = .true.
  parr (1) = .false.
  parr (4 : size(parr) : 2) = .false.
  do i = 3, int (sqrt (real (size(parr)))), 2
    if (parr(i)) parr(i * i : size(parr) : i) = .false.
  end do
 
end subroutine
 
function is_rtp(candidate)
  logical :: is_rtp
  integer, intent(in) :: candidate
  integer :: n
 
  is_rtp = .true.
  n = candidate / 10
  do while(n > 0)
    if(.not. primes(n)) then
      is_rtp = .false.
      return
    end if
    n = n / 10
  end do
 
end function
 
function is_ltp(candidate)
  logical :: is_ltp
  integer, intent(in) :: candidate
  integer :: i, n
  character(10) :: nstr
 
  write(nstr, "(i10)") candidate
  is_ltp = .true.
  do i = len_trim(nstr)-1, 1, -1
    n = mod(candidate, 10**i)
    if(.not. primes(n)) then
      is_ltp = .false.
      return
    end if
  end do
end function
 
end module primes_mod
 
program Truncatable_Primes
  use primes_mod
  implicit none
 
  integer, parameter :: limit = 999999
  integer :: i
  character(10) :: nstr
 
! Generate an array of prime flags up to limit of search
  allocate(primes(limit))
  call Genprimes(primes)
 
! Find left truncatable prime
  do i = limit, 1, -1
    write(nstr, "(i10)") i
    if(index(trim(nstr), "0") /= 0) cycle      ! check for 0 in number
    if(is_ltp(i)) then
      write(*, "(a, i0)") "Largest left truncatable prime below 1000000 is ", i
      exit
    end if
  end do
 
! Find right truncatable prime
  do i = limit, 1, -1
    write(nstr, "(i10)") i
    if(index(trim(nstr), "0") /= 0) cycle      ! check for 0 in number
    if(is_rtp(i)) then
      write(*, "(a, i0)") "Largest right truncatable prime below 1000000 is ", i
      exit
    end if
  end do
end program