Project Euler Problem 87 Solution

Project Euler Problem 87

Problem Description :

    

      The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

28 = 2² + 2³ + 2⁴
33 = 3² + 2³ + 2⁴
49 = 5² + 2³ + 2⁴
47 = 2² + 3³ + 2⁴

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

Solution :

     Roughly we have to generate prime numbers up to 10000. There are 1229 prime numbers bellow 10000. After generating these primes using a n^3 loop we can count the number of ways. Of-course we have to also check duplication of answers.

C++ Implementation of this problem.

#include <cstdio>
#include <iostream>

using namespace std;

#define fiftyMillion 50000001
#define sz 10001
#define mx 101
bool p[sz],ans[fiftyMillion+2];
long primeTable[1230],ind = 0;

void sieve(){
 long i,j;

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

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

int main(){
 long i,j,k,l,cnt=0;
 long sum,S,Q,F;

 sieve();

 //printf("%ld\n",ind);

 for(i = 0;i < ind;i++){  
  S = primeTable[i] * primeTable[i];
  if(S>fiftyMillion)
   break;
  for( j = 0; j < ind; j++){   
   Q =  primeTable[j] * primeTable[j] * primeTable[j];
   if(Q+S>fiftyMillion)
    break;
   for(k = 0; k < ind; k++){
    F =  primeTable[k] * primeTable[k] * primeTable[k] * primeTable[k]; 
    if(F+Q+S>fiftyMillion)
     break;
    sum = S + Q + F;
    if(!ans[sum]){
     cnt++;
     ans[sum] = true;
    }    
   }
  }

 }
 printf("%ld\n",cnt);

 return 0;
}