Project Euler : Largest N Digit Pandigital Prime Number

Well, I did a brute force for problem 41 for Project Euler. There’s a smarter way of course, but I still haven’t implemented a Permutation Generator. That later.

I already have a good enough prime number generator. So all I did was to generate all the prime number till 7 digits long. Why did I not go any further?

8 digit pandigital numbers will sum up to 36, and the 9 digit numbers will sum up to 45. So all the pandigital 8 and 9 digit numbers will be non-prime. So we need to check till atmost the 7 digit prime numbers.

Now apart from a prime generator, I also have a prime number iterator, which can iterate forwards as well as backwards. So all I had to do was to ask my iterator to iterate backwards and check if the prime number is pandigital or not.

Obviously, my prime number iterator internally calls my sieve of Eratosthenes to generate prime numbers using java.util.BitSet.

Surprisingly, the code runs in just a few seconds! I was expecting it to take atleast a minute.

Here is my prime number iterator:

public class PrimeNumbersIterator implements Iterator<Integer> {
	private PrimeNumbers m_pNumber;
	private int m_currentIndex;
	private boolean m_reverse;

	public PrimeNumbersIterator(int upperLimit) {
		m_pNumber = new PrimeNumbers(upperLimit);
		m_reverse = false;
	}

	public boolean hasNext() {
		if (!m_reverse)
			return m_currentIndex < m_pNumber.getNumberOfPrimes() ? true : false;
		else
			return m_currentIndex >= 0 ? true : false;
	}

	public Integer next() {
		Integer prime = hasNext() ? m_pNumber.getPrime(m_currentIndex) : null;
		if (m_reverse)
			m_currentIndex--;
		else
			m_currentIndex++;

		return prime;
	}

	public void remove() {
		throw new UnsupportedOperationException();
	}

	public void reverseOrder() {
		m_reverse = !m_reverse;
		m_currentIndex = m_pNumber.getNumberOfPrimes() - 1;
	}
}

And here is a small unoptimized method to check if the number is pandigital or not:

	public static boolean isNPandigital(int number) {
		int numberOfDigits = NumberUtil.numberOfDigits(number);
		int[] digits = new int[numberOfDigits];
		Arrays.fill(digits, 0);

		while (number > 0) {
			int digit = number % 10;
			if (digit == 0 || digit > numberOfDigits || digits[digit - 1]++ == 1)
				return false;
			number /= 10;
		}

		return true;
	}

Popularity: 38% [?]

Related posts:

1. Project Euler : Problem 32 – All Round Pandigital
2. Project Euler : Find the nth Prime
3. Project Euler : Finding The Largest Prime Factor Of A Given Number
4. Project Euler : Adding 100 50-Digit Numbers
5. Project Euler : Sum Of Digits In a^b