[C/C++] Project Euler #41 - Pandigital Prime

This problem has a difficulty rating of 5%. It’s not a particularly difficult problem.

 

Let’s take a look at the problem.

 

A number is called a pandigital number if it contains each digit from 1 to n exactly once. For example, 2143 is a 4-digit pandigital number, and it is also a prime.

 

What is the largest n-digit pandigital prime?

---

Since we are looking for a pandigital number, we need to use each digit from 1 to n exactly once.

The largest possible number of digits for a pandigital number is 9 because, beyond that, the number would have more than 9 digits, which would violate the definition of a pandigital number.

 

The program should generate all possible pandigital numbers starting from the largest 9-digit number. (In essence, this means generating all permutations of numbers from 1 to n). While the last digit of the number should ideally not be an even number or 5 (to avoid non-prime numbers), this approach ignores such cases for simplicity.

 

There are multiple ways to generate permutations, but here, a recursive function was used, checking from the largest number downwards.

---

pandigital numbers

---

A simple program to achieve this would look like the following:

//------------------------------------------------
//    Project Euler #41 - Pandigital Prime
//        - by Aubrey Choi
//        - created at 2015-03-27
//------------------------------------------------
#include <stdio.h>
#include "isprime.h"

uint64_t TestAndReturn(uint64_t n, uint64_t m, int r, int c = 9);

int main()
{
    for( int i = 9 ; ; i-- )
    {
        uint64_t res = TestAndReturn(0, 0, i, i);
        if( res == 0 ) continue;
        printf("ans = %ju\n", res);
        break;
    }
}


uint64_t TestAndReturn(uint64_t n, uint64_t m, int r, int c)
{
    if( r == 0 )
    {
        if( isPrime(n) ) return n;
        return 0;
    }
    for( int i = c ; i > 0 ; i-- )
    {
        if( (m>>i) & 1 ) continue;
        uint64_t res = TestAndReturn(n*10+i, m|(1<<i), r-1, c);
        if( res ) return res;
    }
    return 0;
}

 

This program solves Project Euler Problem #41 - Pandigital Prime.

 

It finds the largest n-digit pandigital prime by generating permutations and checking for the largest prime number.

---

Code Structure and Explanation

 

1. main() function
• Starts with i = 9 and decrements i in each iteration.
• Calls TestAndReturn() to find the largest pandigital prime.
• If TestAndReturn() returns a nonzero value, prints the result and exits.

 

2. TestAndReturn(uint64_t n, uint64_t m, int r, int c) function
• Recursively generates pandigital numbers by constructing n digit by digit.
• When r == 0, checks if n is a prime number.
• Uses a for loop iterating from c to 1 to select possible digits.
• Uses m as a bitmask to track used digits.
• If a valid prime is found (res != 0), returns that number.

---

Key Logic

 

1. TestAndReturn() starts from 9 and generates all pandigital numbers.
2. It checks the largest numbers first and returns the first prime found.
3. isPrime() function determines if a number is prime.
4. The bitmask technique (m|(1<<i)) ensures that digits are used only once.

---

Expected Execution Flow

 

1. i = 9, calls TestAndReturn(0, 0, 9, 9).
2. Generates 9-digit pandigital numbers from largest to smallest.
3. Checks for primality and returns the largest prime found.
4. Prints the result and terminates.