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


fn is_prime(n: u32) -> bool {
    if n < 2 {
        return false;
    }
    if n % 2 == 0 {
        return n == 2;
    }
    if n % 3 == 0 {
        return n == 3;
    }
    let mut p = 5;
    while p * p <= n {
        if n % p == 0 {
            return false;
        }
        p += 2;
        if n % p == 0 {
            return false;
        }
        p += 4;
    }
    true
}
 
fn is_left_truncatable(p: u32) -> bool {
    let mut n = 10;
    let mut q = p;
    while p > n {
        if !is_prime(p % n) || q == p % n {
            return false;
        }
        q = p % n;
        n *= 10;
    }
    true
}
 
fn is_right_truncatable(p: u32) -> bool {
    let mut q = p / 10;
    while q > 0 {
        if !is_prime(q) {
            return false;
        }
        q /= 10;
    }
    true
}
 
fn main() {
    let limit = 1000000;
    let mut largest_left = 0;
    let mut largest_right = 0;
    let mut p = limit;
    while p >= 2 {
        if is_prime(p) && is_left_truncatable(p) {
            largest_left = p;
            break;
        }
        p -= 1;
    }
    println!("Largest left truncatable prime is {}", largest_left);
    p = limit;
    while p >= 2 {
        if is_prime(p) && is_right_truncatable(p) {
            largest_right = p;
            break;
        }
        p -= 1;
    }
    println!("Largest right truncatable prime is {}", largest_right);
}