Project Euler Problem 41

Problem 41

11 April 2003

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?

Answer: 7652413

 

 

C#

 

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

namespace Euler {
    class Program {
        static bool isPrime(int value) {
            if (value <= 1) return false;
            for (int i = 2; i * i <= value; i++) {
                if (value % i == 0) return false;
            }
            return true;
        }

        static string arrayToString<T>(T[] array) {
            return array.Select(x => Convert.ToString(x)).Aggregate(string.Concat);
        }

        static void permute(int[] n, int level = 0) {
            if (level > n.Length - 1) {
                //Console.Write(count + ": ");
                //foreach (var x in n) Console.Write(x);
                //Console.WriteLine();
                //Console.ReadKey();
                var num = Convert.ToInt32(arrayToString(n));
                if (isPrime(num)) {
                    Console.WriteLine(num);
                    Environment.Exit(0);
                }
                return;
            }
            for (int i = n.Length; i >= 1; i--) {
                bool hasDuplicate = false;
                for (int priorLevel = 0; priorLevel < level; priorLevel++) {
                    if (i == n[priorLevel]) {
                        hasDuplicate = true;
                        break;
                    }
                }
                if (!hasDuplicate) {
                    n[level] = i;
                    permute(n, level + 1);
                }
            }
        }

        static void Main(string[] args) {            
            for (int i = 9; i >= 1; i--) {
                permute(new int[i]);
            }
        }
    }
}