Project Euler Problem 77 Solution

Problem Description :

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

Solution :
  At first I have tried to find out the solution using primes bellow 1 million. But the ans is 71. So we have to generate primes up to 100(roughly). Then using these number and a special computing technique called coin change logic which is one kind of dynamic programming paradigm, we can solved this problem.


     Here every primes up to 100 is a coin. Now the question is for which key we can add up coins over five hundred ways. See implementation for this idea.


     Here is the C++ implementation of the problem.

#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;

#define sz 101
#define mx 11

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

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;
  }
 }
}




int main(){
 long i,cnt = 0,high,key,j;

 bool f = true;
 sieve();
 ans[0] = 1;

 for(i = 0; i < nPrime && f; i++){
  high = 100 - primeTable[i];
  for(j = 0; j < high; j++){
   if(ans[j]){
    ans[j+primeTable[i]] += ans[j];    
   }
  }
 }
 for(i = 0; i < 100; i++){
  if(ans[i] >= 5000){
   printf("%ld\n",i);
   break;
  }
 }


 return 0;
}