Problem Analysis
An n-digit number is pandigital if it uses each of the digits 1 through n exactly once. I want the largest such number that is also prime. The brute-force formulation is clear: for every length from 1 to 9, generate every permutation of the digit set, test each for primality, and take the maximum. That is feasible - the largest length, 9, has only 9! = 362880 arrangements - but a single piece of number theory collapses almost all of the work before I write a search loop.
The decisive observation is the divisibility rule for 3: a number is divisible by 3 exactly when the sum of its digits is divisible by 3. For an n-digit pandigital number, the digit sum does not depend on the arrangement - it is the triangular number n(n+1)/2. Evaluating it: n=9 gives 45, n=8 gives 36, n=6 gives 21, n=5 gives 15, n=3 gives 6, n=2 gives 3 - all divisible by 3, so every pandigital of those lengths is composite. Only n=1 (sum 1, but the value 1 is not prime), n=4 (sum 10), and n=7 (sum 28) survive. That single analytic step cuts nine candidate lengths down to two. What remains is to enumerate the permutations of {1,2,3,4} and {1,2,3,4,5,6,7} - 4! = 24 and 7! = 5040 candidates - and test each for primality. Since the largest candidate is below 8 million, trial division up to the square root (about 2800) is far more than fast enough. The overall complexity is O(k! * sqrt(N)) with k at most 7 - microseconds in practice.
Solution Approach
Descending Permutation Search (C and Python)
Both files implement the same algorithm: enumerate the permutations of each viable digit set in descending numeric order, length 7 before length 4, and return the first arrangement that passes a primality test. Because I walk from the largest value downward, the first prime I encounter is necessarily the largest pandigital prime - there is no need to collect every prime and take a maximum. This turns "find the maximum element with property P" into "stop at the first match", which holds the result count at one and avoids any sorting.
In the C version I store the surviving lengths as the literal array {7, 4}, encoding the digit-sum pruning conclusion directly in the code. For each length I initialise the digit array in descending order (7,6,5,4,3,2,1) and then call prev_permutation after every test. prev_permutation is the mirror image of the classic next_permutation: it finds the rightmost position where the array descends, swaps that element with the largest element smaller than it in the tail, and reverses the tail - producing every arrangement in strictly descending lexicographic order, in O(n) time and O(1) extra space per step. (The file also carries a forward next_permutation for symmetry, though the search itself only uses the descending walk.) The helper digits_to_number folds the digit array into an integer with the standard num = num * 10 + digit accumulation, keeping the number-building step cleanly separate from the primality test. The test itself, is_prime, handles 2 specially, rejects evens, then trial-divides by odd numbers up to the square root, guarding the multiplication with long long to avoid overflow.
The Python version achieves the same descending order by reversing the digit tuple before handing it to itertools.permutations. Since permutations yields its results in the lexicographic order of its input, feeding it ("7","6",...,"1") produces numbers in descending order. The candidates are formed with int("".join(digits)) and filtered lazily inside a generator expression; next() pulls the first prime and abandons the rest. The is_prime routine is identical in spirit to the C one, and fast_is_prime is a thin alias kept only for naming parity with other solutions.