Wednesday 4 September 2013

PROJECT EULER SOLUTION # 50

Solution to problem number 50 of Project Euler.
Question # 50

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
Solution # 50
/***********************************************************************************************************/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>

int is_prime(long);

int is_prime(long n)
{
       int i=2;
       for(i=2;i<=(long)sqrt((double)n);i++)
              if(n%i==0)
                     return 0;
       return 1;
}

int main()
{
       long i,j,sum=0,temp_terms=0,terms=0,ans=0,temp,num=1000,a,actual_sum=0;
       for(i=2;i<num && ans<num;i++)
       {
              if(is_prime(i))
              {
                     sum=0;
                     temp_terms=0;
                     a=0;
                     for(j=i;;j++)
                     {
                          
                           temp=sum;
                    
                           if(is_prime(j))
                           {
                                  a++; // a counts the sequence of primes...
                                  sum+=j;
                                  if(sum>=num)
                                         break;
                                  if(is_prime(sum))
                                  {
                                         actual_sum=sum;
                                         temp_terms=a;
                                  }
                           }
                     }
                     if(temp_terms>terms)
                     {
                           terms=temp_terms;
                           ans=actual_sum;
                     }
              }
       }

       printf("%d\n",ans);
       printf("Execution time = %f\n",clock()/(float)CLK_TCK);
       system("pause");
}
/***********************************************************************************************************/


No comments:

Post a Comment