I recently finished the 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?
And I'm having trouble optimizing it.
Explanation
So we know that the upper bound should be a maximum of 987654321 which is the biggest pandigital number it's not a prime however so we probably can lower this but for now let's keep it like this.
We are working with primes and more specifically pandigital primes. First we need an algorithm that calculates all the primes up to our upper limit (987654321 ), I went for the sieve of Eratosthenes :
bool[] primes = SetPrimes(987654321);
private static bool[] SetPrimes(int max)
{
bool[] localPrimes = new bool[max + 1];
for (long i = 2; i <= max; i++)
{
localPrimes[i] = true;
}
for (long i = 2; i <= max; i++)
{
if (localPrimes[i])
{
for (long j = i*2; j <= max; j += i)
{
localPrimes[j] = false;
}
}
}
return localPrimes;
}
Good those are all the primes that we will need now all that's left is to implement a pandigital number checker and iterate through the boolean array :
private static bool IsPandigital(long input)
{
char[] digits = input.ToString().ToCharArray();
for (int i = 1; i <= input.ToString().Length; i++)
{
int count = digits.Count(x => char.GetNumericValue(x) == i);
if (count != 1)
{
return false;
}
}
return true;
}
Pretty simple check just taking the current index of the primes array, convert's it to a char array and we know that a pandigital number is that number that it has each from 1 to it's length exactly one (1, number.Length) so we do that in the for loop and than we check if it's contained exactly once if so we return true
else we return false
.
Lastly we iterate through the array of prime :
long lastIndex = Array.LastIndexOf(primes, true);
while (!IsPandigital(lastIndex))
{
lastIndex--;
while (!primes[lastIndex])
{
lastIndex--;
}
}
Here we take the last index that has true value (the last prime number) and than we start decreasing the index that we are looking for if we incur a number that is pandigital and it's prime we just break out of all the loops and print it on the screen. It's currently running for about 75-78k milliseconds which really bothers me that's a lot of time. Any improvements concerning the performance and the code style are welcome.
Full Code :
private static void Main()
{
Stopwatch sw = Stopwatch.StartNew();
bool[] primes = SetPrimes(987654321);
long lastIndex = Array.LastIndexOf(primes, true);
while (!IsPandigital(lastIndex))
{
lastIndex--;
while (!primes[lastIndex])
{
lastIndex--;
}
}
sw.Stop();
Console.WriteLine(lastIndex);
Console.WriteLine("Time to calculate in milliseconds : {0}", sw.ElapsedMilliseconds);
Console.ReadKey();
}
private static bool[] SetPrimes(int max)
{
bool[] localPrimes = new bool[max + 1];
for (long i = 2; i <= max; i++)
{
localPrimes[i] = true;
}
for (long i = 2; i <= max; i++)
{
if (localPrimes[i])
{
for (long j = i*2; j <= max; j += i)
{
localPrimes[j] = false;
}
}
}
return localPrimes;
}
private static bool IsPandigital(long input)
{
char[] digits = input.ToString().ToCharArray();
for (int i = 1; i <= input.ToString().Length; i++)
{
int count = digits.Count(x => char.GetNumericValue(x) == i);
if (count != 1)
{
return false;
}
}
return true;
}