[SOLUTION] Google Treasure Hunt - Primes

Here comes the II. quest from Google Treasure Hunt. Maybe it sounds very simple, and algorithm what we've (Szakál Károly (ftnkaresz /at gmail /dot com) and I) used isn't so difficult, but after 3 hours of hard-coding, what we got? A full stack error with 2GB RAM. ;)

Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 9 consecutive prime numbers,
the sum of 253 consecutive prime numbers,
the sum of 781 consecutive prime numbers,
and is itself a prime number.

For example, 41 is the smallest prime number that can be expressed as
the sum of 3 consecutive primes (11 + 13 + 17 = 41) and
the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).


Recursion is very bad thing in programming. It isn't requires deeper analysis of problems, there is enough to make good type definitions, a good algorithm with some recursive calls and return statement and finally there recursion will solve the problem for you. Okay! :)
The main goal of Data Structure and Algorithms is how to solve problems without recursive calls, and how to avoid the whole recursion.
The first solution made without recursion in programming language C. The main part of this program is an infinite while loop, what terminates itself if the right prime sum found:

while(1) {
switch (r) {
case 0: result=PrimSum(previousPrime,1063,&previousPrime);
ix=0;
nextPrime=2;
r=sum(nextPrime,1063,result);
break;
case 1: ix++;
if (!(ix<5)) { return 0; }
nextPrime=2;
r=sum(nextPrime,array[ix],result);
break;
case 2: r=sum(nextPrime=NextPrim(nextPrime),array[ix],result);
break;
}
}



Finally, our number is: 6304483.

The full sorce code:

#include
#include
#include
//4355977//d9062d
const int array[]={1063,309,183,137,5};
int ix=0;

int nPrimSum(int,int);
int PrimSum(int,int,int*);
int isPrime(int);
int sum(int,int,int);
int NextPrim(int);

int main()
{int result, r=0;
int previousPrime=2, nextPrime=2;

while(1) {
switch (r) {
case 0: result=PrimSum(previousPrime,1063,&previousPrime);
ix=0;
nextPrime=2;
r=sum(nextPrime,1063,result);
break;
case 1: ix++;
if (!(ix < 5)) { return 0; }
nextPrime=2;
r=sum(nextPrime,array[ix],result);
break;
case 2: r=sum(nextPrime=NextPrim(nextPrime),array[ix],result);
break;
} //switch
} //while

return 0;
}
int isPrime(int xx) {
double i;
double a=sqrt(xx);

for(i=2; i<=a; i++) {
if (!(xx%((int)i))) return 0;
}
return 1;
}


int NextPrim(int pr) {
int i;
for(i=pr+1; !(isPrime(i)); i++);
return i;
}

int PrimSum(int min, int step, int *ePrim) {
int i,ret;
for(i=min; !(isPrime(ret=nPrimSum(i,step))); i=NextPrim(i))
;
*ePrim=NextPrim(i);
return ret;
}

int nPrimSum(int min, int step) {
int i=0;
int numb=min, summ=0;

while (i < step) {
if (isPrime(numb)) {
summ+=numb;
i++;
}
numb++;
}

return summ;
}
//----------------------------------------------------

int sum(int min, int step, int sum_n) {
int i=0;
int numb=min, summ=0;

while (i < step) {
if (isPrime(numb)) {
summ+=numb;
i++;
}
numb++;
}

if (summ==sum_n) return 1;
if (summ if (summ>sum_n) { return 0; }
}

0 comments: