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


USING: formatting fry grouping.extras kernel literals math
math.parser math.primes sequences ;
IN: rosetta-code.truncatable-primes
 
CONSTANT: primes $[ 1,000,000 primes-upto reverse ]
 
: number>digits ( n -- B{} ) number>string string>digits ;
 
: no-zeros? ( seq -- ? ) [ zero? not ] all? ;
 
: all-prime? ( seq -- ? ) [ prime? ] all? ;
 
: truncate ( seq quot -- seq' ) call( seq -- seq' )
    [ 10 digits>integer ] map ;
 
: truncate-right ( seq -- seq' ) [ head-clump ] truncate ;
 
: truncate-left ( seq -- seq' ) [ tail-clump ] truncate ;
 
: truncatable-prime? ( n quot -- ? ) [ number>digits ] dip
    '[ @ all-prime? ] [ no-zeros? ] bi and ; inline
 
: right-truncatable-prime? ( n -- ? ) [ truncate-right ]
    truncatable-prime? ;
 
: left-truncatable-prime? ( n -- ? ) [ truncate-left ]
    truncatable-prime? ;
 
: find-truncatable-primes ( -- ltp rtp )
    primes [ [ left-truncatable-prime?  ] find nip ]
           [ [ right-truncatable-prime? ] find nip ] bi ;
 
: main ( -- ) find-truncatable-primes
    "Left: %d\nRight: %d\n" printf ;
 
MAIN: main