Project Euler Problem #41

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  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 exa

You can exclude all n-digit pandigitals for n = 2,3,5,6,8,9 since they cannot be prime due to the Divisibility by 3 or 9 rule.

There only the 4-digit and 7-digit numbers left.

Since you need only the largest pandigital number, it makes sense to scan down starting from the largest 7-digit pandigital number.

My implementation of IsPandigital method:

private static bool IsPandigital(int number)
{
    int maxDigit = (int)Math.Log10(number) + 1;
    int allBitsExceptBitOne = (1  maxDigit || (digitBits & mask) != 0)
            return false;
        digitBits |= mask;
        number /= 10;
    }
    return digitBits == allBitsExceptBitOne;
}

Sieve of Eratosthenes:

private static int[] GetPrimes(int n)
{
    BitArray a = new BitArray(n + 1, true);

    int sqrtn = (int)Math.Sqrt(n);
    for (int i = 2; i  primes = new List();
    for (int i = 2; i < a.Length; i++)
    {
        if (a[i])
            primes.Add(i);
    }

    return primes.ToArray();
}

Usage:

const int Max = 7654321;

var primes = GetPrimes(Max);
Array.Reverse(primes);

Console.WriteLine(primes.First(IsPandigital));

StackExchange Code Review Q#125560, answer score: 2