Project Euler Problem 37 Solution

Project Euler Problem 37 Solution

   Problem Description :

   The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

  Solution :
     Here, for the number 3797 we have to check if these (3797,379,7,37,97,3,797) numbers are prime or not. If we carefully see these numbers we can find a easy procedure to truncate numbers.
  Here is the procedure,

• 3797 / 10 = 379  and 3797 % 10 = 7
• 3797 / 100 = 37  and 3797 % 100 = 97
• 3797 / 1000 = 3 and 3797 % 1000 = 797

Now, we have to just find out primes and using this procedure we can check for the truncatable prime.

  Here is the C++ implementation of the solution.

#include <cstdio>
#include <iostream>

using namespace std;

#define sz 1000001
#define mx 1001

bool p[sz];
long primeTable[78500],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 isTruncatable(long n){
 long pow = 10;

 while( pow < n){
  if(p[n%pow] || p[n/pow])
   return false;
  pow *= 10;
 }

 return true;
}


int main(){
 long i,ans = 0;

 sieve();

 printf("Number of primes bellow 1 million is %ld\n",nPrime);

 for( i = 4; i < nPrime; i++){
  if( isTruncatable(primeTable[i]) ){
   ans += primeTable[i];
   printf("%ld\n",primeTable[i]);
  }
 }

 printf("Sum of 11 truncatable primes is %ld\n",ans);


 return 0;
}

Output :