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


 
# syntax: GAWK -f TRUNCATABLE_PRIMES.AWK
BEGIN {
    limit = 1000000
    for (i=1; i<=limit; i++) {
      if (is_prime(i)) {
        prime_count++
        arr[i] = ""
        if (truncate_left(i) == 1) {
          max_left = max(max_left,i)
        }
        if (truncate_right(i) == 1) {
          max_right = max(max_right,i)
        }
      }
    }
    printf("1-%d: %d primes\n",limit,prime_count)
    printf("largest L truncatable: %d\n",max_left)
    printf("largest R truncatable: %d\n",max_right)
    exit(0)
}
function is_prime(x,  i) {
    if (x <= 1) {
      return(0)
    }
    for (i=2; i<=int(sqrt(x)); i++) {
      if (x % i == 0) {
        return(0)
      }
    }
    return(1)
}
function truncate_left(n) {
    while (n != "") {
      if (!(n in arr)) {
        return(0)
      }
      n = substr(n,2)
    }
    return(1)
}
function truncate_right(n) {
    while (n != "") {
      if (!(n in arr)) {
        return(0)
      }
      n = substr(n,1,length(n)-1)
    }
    return(1)
}
function max(x,y) { return((x > y) ? x : y) }
 