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


package require Tcl 8.5
 
# Optimized version of the Sieve-of-Eratosthenes task solution
proc sieve n {
    set primes [list]
    if {$n < 2} {return $primes}
    set nums [dict create]
    for {set i 2} {$i <= $n} {incr i} {
        dict set nums $i ""
    }
    set next 2
    set limit [expr {sqrt($n)}]
    while {$next <= $limit} {
        for {set i $next} {$i <= $n} {incr i $next} {dict unset nums $i}
        lappend primes $next
	dict for {next -} $nums break
    }
    return [concat $primes [dict keys $nums]]
}
 
proc isLeftTruncatable n {
    global isPrime
    while {[string length $n] > 0} {
	if {![info exist isPrime($n)]} {
	    return false
	}
	set n [string range $n 1 end]
    }
    return true
}
proc isRightTruncatable n {
    global isPrime
    while {[string length $n] > 0} {
	if {![info exist isPrime($n)]} {
	    return false
	}
	set n [string range $n 0 end-1]
    }
    return true
}
 
# Demo code
set limit 1000000
puts "calculating primes up to $limit"
set primes [sieve $limit]
puts "search space contains [llength $primes] members"
foreach p $primes {
    set isPrime($p) "yes"
}
set primes [lreverse $primes]
 
puts "searching for largest left-truncatable prime"
foreach p $primes {
    if {[isLeftTruncatable $p]} {
	puts FOUND:$p
	break
    }
}
 
puts "searching for largest right-truncatable prime"
foreach p $primes {
    if {[isRightTruncatable $p]} {
	puts FOUND:$p
	break
    }
}