PROJECT EULER #37

Link to Project Euler problem 37

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

using System;

namespace project_euler
{
class Program
{
    static void Main()
    {
        //Problem 37
        DateTime start = DateTime.Now;
        int sum = 0;
        for (int i = 9; i < 1000000; i+=2)
        {
            string s = i.ToString();
            if (!s.Contains("0") || !s.Contains("4") || !s.Contains("6") || !s.Contains("8"))
            {
                bool test = true;
                for (int j = 0; j < s.Length; j++)
                    if (!IsPrime(int.Parse(s.Substring(j, s.Length - j))) || !IsPrime(int.Parse(s.Substring(0, j + 1))))
                        test = false;
                if (test)
                    sum += i;
            }
        }
        Console.WriteLine(sum);
        TimeSpan time = DateTime.Now - start;
        Console.WriteLine("This took {0}", time);
        Console.ReadKey();
    }
    //test if prime
    public static bool IsPrime(int n)
    {
        if (n < 2)
            return false;
        if (n == 2)
            return true;
        for (long i = 2; i <= Math.Sqrt(n); i++)
            if (n % i == 0)
                return false;
        return true;
    }
}
}