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 System;  // 4790@3.6
using System.Collections.Generic;
class truncatable_primes
{
    static void Main()
    {
        uint m = 1000000;
        Console.Write("L " + L(m) + " R " + R(m) + "  ");
        var sw = System.Diagnostics.Stopwatch.StartNew();
        for (int i = 1000; i > 0; i--) { L(m); R(m); }
        Console.Write(sw.Elapsed); Console.Read();
    }
 
    static uint L(uint n)
    {
        n -= n & 1; n--;
        for (uint d, d1 = 100; ; n -= 2)
        {
            while (n % 3 == 0 || n % 5 == 0 || n % 7 == 0) n -= 2;
            if ((d = n % 10) == 3 || d == 7)
            {
                while (d1 < n && d < (d = n % d1) && isP(d)) d1 *= 10;
                if (d1 > n && isP(n)) return n; d1 = 100;
            }
        }
    }
 
    static uint R(uint m)
    {
        var p = new List<uint>() { 2, 3, 5, 7 }; uint n = 20, np;
        for (int i = 1; i < p.Count; n = 10 * p[i++])
        {
            if ((np = n + 1) >= m) break; if (isP(np)) p.Add(np);
            if ((np = n + 3) >= m) break; if (isP(np)) p.Add(np);
            if ((np = n + 7) >= m) break; if (isP(np)) p.Add(np);
            if ((np = n + 9) >= m) break; if (isP(np)) p.Add(np);
        }
        return p[p.Count - 1];
    }
 
    static bool isP(uint n)
    {
        if (n < 7) return n == 2 || n == 3 || n == 5;
        if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0) return false;
        for (uint r = (uint)Math.Sqrt(n), d = 7; d <= r; d += 30)
            if (n % (d + 00) == 0 || n % (d + 04) == 0 ||
                n % (d + 06) == 0 || n % (d + 10) == 0 ||
                n % (d + 12) == 0 || n % (d + 16) == 0 ||
                n % (d + 22) == 0 || n % (d + 24) == 0) return false;
        return true;
    }
}