CS19002 Programming and Data Structures Laboratory, Section 5

Spring 2007

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 = a2 + b2 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 = a2 + b2,

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");
      printf("************* Part 2 *************\n");

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


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

Submission site  |  Show solution  |  Hide solution ]

Back  |  Home