Project Euler Problem #41!

July 26th, 2009
by Serinox

Problem #41 says:

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 pan-digital and is also prime.

What is the largest n-digit pan-digital prime that exists?

I did this problem as a battery life test for my new Acer Timeline 3810t so its a brute-force solution with very little optimization, and took about 3 hours to run (which only took half my battery!). Solution is in c# pretty simple and straight forward nothing took fancy. Generate all of the primes from 1 to 999,999,999 and check to see which are N-digit pan-digital. Solution in c#/mono.

Here’s a hint for people running this program, the solution has 7 digits (so you only need to check upto 9,999,999) which can be done in ~20 seconds using this code.

using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEuler
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            ArrayList primes = GeneratePrimes(9999999);
            long Answer = 0;
            foreach (long p in primes)
            {
                if (IsNPandigital(p) == 1 && p > Answer)
                {
                    Answer = p;
                }
            }
            Console.WriteLine(Answer);
            sw.Stop();
            Console.WriteLine(sw.Elapsed);
            Console.ReadLine();
        }
        static ArrayList GeneratePrimes(long num)
        {
            ArrayList RetValue = new ArrayList();
            RetValue.Add((long)2);
            RetValue.Add((long)3);
            long Stepper = 5;
            long Check = 1;
            while (Stepper <= num)
            {
                foreach (long i in RetValue)
                {
                    if (Stepper % i == 0)
                    {
                        Check = 0;
                        break;
                    }
                    if (Math.Sqrt(Stepper) < i)
                    {
                        break;
                    }
                }
                if (Check == 1)
                {
                    //Console.WriteLine(((float)Stepper / (float)num) * 100);
                    RetValue.Add(Stepper);
                }
                Check = 1;
                Stepper++;
                Stepper++;
            }
            return RetValue;
        }
        static int IsNPandigital(long i)
        {
            char[] I = i.ToString().ToCharArray();
            long[] counters = new long[9] { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
            int length = i.ToString().Length;
            foreach (char c in I)
            {
                switch (c)
                {
                    case '1':
                        counters[0] += 1;
                        break;
                    case '2':
                        counters[1] += 1;
                        break;
                    case '3':
                        counters[2] += 1;
                        break;
                    case '4':
                        counters[3] += 1;
                        break;
                    case '5':
                        counters[4] += 1;
                        break;
                    case '6':
                        counters[5] += 1;
                        break;
                    case '7':
                        counters[6] += 1;
                        break;
                    case '8':
                        counters[7] += 1;
                        break;
                    case '9':
                        counters[8] += 1;
                        break;
                }
            }
            int LCheck = 0;
            foreach (long Check in counters)
            {
                if (LCheck < length)
                {
                    if (Check > 1)
                        return -1;
                    if (Check == 0)
                        return 0;
                    LCheck++;
                }
            }
            return 1;
        }
    }
}

Posted in Project Euler | Comments (0)

No comments yet

Leave a Reply

You must be logged in to post a comment.