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


code CrLf=9, IntOut=11;
 
func Prime(P);          \Return true if P is a prime number
int  P;                 \(1 is not prime, but 2 is, etc.)
int  I;
[if P<=1 then return false;     \negative numbers are not prime
for I:= 2 to sqrt(P) do
        if rem(P/I) = 0 then return false;
return true;
];
 
func RightTrunc(N);     \Return largest right-truncatable prime < one million
int N;
int M;
[for N:= 1_000_000-1 downto 2 do
        [M:= N;
        loop    [if not Prime(M) then quit;
                M:= M/10;
                if rem(0) = 0 then quit;        \no zeros allowed
                if M=0 then return N;
                ];
        ];
];
 
func LeftTrunc(N);      \Return largest left-truncatable prime < one million
int N;
int M, P;
[for N:= 1_000_000-1 downto 2 do
        [M:= N;
        P:=100_000;
        loop    [if not Prime(M) then quit;
                M:= rem(M/P);
                P:= P/10;
                if M<P then quit;               \no zeros allowed
                if M=0 then return N;
                ];
        ];
];
 
[IntOut(0, LeftTrunc);  CrLf(0);
 IntOut(0, RightTrunc); CrLf(0);
]