Assignment 2

---

[ Submission site  |  Show solution  |  Hide solution ]

---

Part 1 [Credit: 80%]

Goldbach's conjecture states that every even integer 2n greater than 2 can be expressed as the sum of two primes. No proof for this conjecture is known. In this part of the assignment, you are asked to verify Goldbach's conjecture for small values of n. Proceed as follows.

Write a function that upon input a positive integer n returns whether n is prime. Notice that 1 is not a prime.

Write another function that takes an integer n > 1 as input and expresses 2n as

   2n = p + q,

where p,q are primes. The function prints this decomposition and returns.

Part 2 [Credit: 20%]

It is known that every prime p of the form 4k+1 can be expressed as p = a² + b² for two integers a,b.

Write a function that, upon input a positive integer n, returns the smallest prime p >= n of the form 4k+1. You may use the first fuction from Part 1 for checking primality.

Write a function that takes a prime p of the form 4k+1, computes a decomposition

   p = a² + b²,

prints this decomposition, and returns.

Your main() function reads an integer n > 1 from the user, calls the function for computing the Goldbach decomposition of 2n, and also the function for computing the sum-of-squares decomposition of the smallest prime p >= n of the form 4k+1. The following is a recommended main() function.

   int main ()
   {
      unsigned long int n;

      printf("Enter a positive integer: ");
      scanf("%lu", &n);
      printf("************* Part 1 *************\n");
      Goldbach(n);
      printf("************* Part 2 *************\n");
      sumofsq(nextprime(n));
   }

Report the output of your program on the following values of n.

   77777
   104729
   1000000
   15485863
   987654321

Sample output

   Enter a positive integer: 1234567890
   ************* Part 1 *************
   Goldbach decomposition: 2469135780 = 19 + 2469135761.
   ************* Part 2 *************
   Sum-of-square decomposition: 1234567913 = 1168^2 + 35117^2

---

Solution

   #include <stdio.h>
   #include <math.h>

   int isprime ( unsigned long int n )
   {
      unsigned long int s, d;

      if ( (n == 0) || (n == 1) ) return 0;
      s = sqrt(n);
      for (d = 2; d <= s; ++d) if (n % d == 0) return 0;
      return 1;
   }

   void Goldbach ( unsigned long int n )
   {
      int p, N;

      if (n == 1) {
         printf("I want n > 1.\n");
         return;
      }
      N = 2 * n;
      for (p = 2; p <= n; ++p) {
         if ((isprime(p)) && (isprime(N-p))) {
            printf("Goldbach decomposition: %lu = %lu + %lu\n", N, p, N-p);
            return;
         }
      }
      printf("Goldbach's conjecture does not hold for %lu\n", N);
   }

   unsigned long int nextprime ( unsigned long int n )
   {
      unsigned long int p;

      p = n - (n % 4) + 1;
      while (!isprime(p)) p += 4;
      return p;
   }

   void sumofsq ( unsigned long int p )
   {
      unsigned long int a, b, s, t;

      s = sqrt(p);
      for (a = 1; a <= s; ++a) {
         t = p - a * a;
         b = sqrt(t);
         if (t == b * b) {
            printf("Sum-of-square decomposition: %lu = %lu^2 + %lu^2\n", p, a, b);
            return;
         }
      }
      printf("I do not find a decomposition. Check your input (%lu).\n", p);
   }

   int main ()
   {
      unsigned long int n;

      printf("Enter a positive integer: ");
      scanf("%lu", &n); printf("%lu\n", n);
      printf("************* Part 1 *************\n");
      Goldbach(n);
      printf("************* Part 2 *************\n");
      sumofsq(nextprime(n));
      printf("\n");
   }

Output

   Enter a positive integer: 77777
   ************* Part 1 *************
   Goldbach decomposition: 155554 = 17 + 155537
   ************* Part 2 *************
   Sum-of-square decomposition: 77797 = 66^2 + 271^2

   Enter a positive integer: 104729
   ************* Part 1 *************
   Goldbach decomposition: 209458 = 17 + 209441
   ************* Part 2 *************
   Sum-of-square decomposition: 104729 = 20^2 + 323^2

   Enter a positive integer: 1000000
   ************* Part 1 *************
   Goldbach decomposition: 2000000 = 7 + 1999993
   ************* Part 2 *************
   Sum-of-square decomposition: 1000033 = 408^2 + 913^2

   Enter a positive integer: 15485863
   ************* Part 1 *************
   Goldbach decomposition: 30971726 = 43 + 30971683
   ************* Part 2 *************
   Sum-of-square decomposition: 15485917 = 1614^2 + 3589^2

   Enter a positive integer: 987654321
   ************* Part 1 *************
   Goldbach decomposition: 1975308642 = 53 + 1975308589
   ************* Part 2 *************
   Sum-of-square decomposition: 987654337 = 11516^2 + 29241^2

---

[ Submission site  |  Show solution  |  Hide solution ]

---

Back  |  Home