Project Euler Problem 41 Solution

Project Euler Problem 41 Solution

Problem Statement :

        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?

Solution :

       We can reduce problem size using the idea that a number will divisible by 3 if the summation of digits of that number is divisible by 3. And if it is true, that number will not be a prime.

       Number of digits                 Summation                       Divisible by 3

                 9                    1+2+3+4+5+6+7+8+9 = 45                     Yes

                 8                       1+2+3+4+5+6+7+8 = 36                     Yes

                 7                          1+2+3+4+5+6+7 = 28                     No

                 6                             1+2+3+4+5+6 = 21                      Yes

                 5                                1+2+3+4+5 = 15                      Yes

                 4                                   1+2+3+4 = 10                      No

       

      As other than 7 digit or 4 digit pandigital number will not be a prime(divisible by 3),We will have to check 7 digit and 4 digit pandigital number only.

     Here is the C++ implementation of the solution.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define sz 2767
#define mx 53

bool p[sz];
int primeTable[sz],nPrime = 0;

void sieve(){
 int i,j;

 p[0] = p[1] = true;
 for( i = 4; i <= sz; i += 2 )
  p[i] = true;

 primeTable[nPrime++] = 2;

 for( i = 3; i <= mx; i += 2 ){
  if(!p[i]){
   primeTable[nPrime++] = i;
   for( j = i * i; j <= sz; j += i )
    p[j] = true;
  }
 }

 for( i = mx + 2; i <= sz; i += 2 ){
  if(!p[i]){
   primeTable[nPrime++] = i;
  }
 }
}

bool isPrime(int n){
 for(int i = 0; i < nPrime; i++ )
  if( n % primeTable[i] == 0)
   return false;

 return true;
}

int main(){
 char num[] = "7654321"; //Largest 7 digit pandigital number

 sieve();
 if(isPrime(atoi(num)))
  printf("%s\n",num);
 else{
  while(prev_permutation( num, num + 7 )){
   if(isPrime(atoi(num))){
    printf("%s\n",num);
    break;
   }
  }
 }

 return 0;
}