# Project Euler

## Pandigital prime

### 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?

First, the largest pandigital number is 987654321. Also, a quick way to know if a number is divisible by 3 is to see if the sum of all the digits is divisible by 3. Therefore, we can check each n-digit pandigital to see if it is possible to contain a prime.

Nay 1+2 = 3 Nay 1+2+3 = 6 Yes 1+2+3+4 = 10 Nay 1+2+3+4+5 = 15 Nay 1+2+3+4+5+6 = 21 Yes 1+2+3+4+5+6+7 = 28 Nay 1+2+3+4+5+6+7+8 = 36 Nay 1+2+3+4+5+6+7+8+9 = 45

Therefore, we should only search 4-digit and 7-digit pandigital number. Since we are looking for the largest pandigital prime, we should start the search at 7654321 and decrement the value by 2 (odd number only) until we found a number that is also a prime. By re-using the prime sieve from problem 37 and the pandigital checker from problem 38, this problem can be solve very quickly.