Sunday 12 April 2009

PROJECT EULER #41

Link to Project Euler problem 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?


I can rule out 9 and 8 digit pandigitals because the sum of the digits is divisible by 9 which means they are not prime

using System;

namespace project_euler
{
class Program
{
static void Main()
{
//Problem 41
DateTime start = DateTime.Now;
string test = "1234567";
int max = 0;
for (int i = 3; i < 7654321; i += 2)
{
string s = i.ToString();
if (!s.Contains("0")||!s.EndsWith("5"))
{
char[] c = s.ToCharArray();
Array.Sort(c);
string t = new string(c);
if (t == test.Substring(0, t.Length))
if (IsPrime(int.Parse(s)))
max = int.Parse(s) > max
? int.Parse(s)
: max;
}
}
Console.WriteLine(max);
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
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;
}
}
}

No comments: