[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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s