PROJECT EULER SOLUTION # 46

Solution to problem number 46 of Project Euler.

Question #46

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 21²
15 = 7 + 22²
21 = 3 + 23²
25 = 7 + 23²
27 = 19 + 22²
33 = 31 + 21²

It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Solution # 46

/***********************************************************************************************************/

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#include<time.h>

int is_prime(long);

 

int main()

{

       long i,j,k;

       int flag;

       for(i=3;;i+=2)

       {

              flag=1;

              if(!is_prime(i))

              {

                     flag=0;

                     for(j=2;j<=i;j++)

                           if(is_prime(j))

                                  for(k=1;k<=i;k++)

                                         if(i==j+2*k*k)

                                         {

                                                flag=1;

                                                goto lavish;

                                         }

              }

              lavish:

              if(!flag)

                     break;

       }

       printf("Answer = %ld\n",i);

       printf("Execution time = %f\n",clock()/(float)CLK_TCK);

       system("pause");

}

int is_prime(long n)

{

       int i;

       for(i=2;i<=(long)sqrt((double)n);i++)

              if(n%i==0)

                     return 0;

       return 1;

}

/***********************************************************************************************************/