Exercise 4-15 - CBD page 168

/**
 * GOLDBACH.C 
 *
 * Exercise solution 2.6.  (C By Dissection Chap. 4, ex. 15)
 *
 * Tests Goldbach's Conjecture on an interval.
 * 26-Feb-03 by Dimon
 **/


/**
 * INCLUDE statements 
 **/
#include "primes.h"


/**
 * DEFINE statements 
 **/
#define BEGIN 0
#define END 1500


/**
 * The main function
 **/
int main(void) {  
  
  /* Declaration of variables */

  int number, firstPrime, lastPrime; 
  int status = 0;


  /* Display program header */
  
  printf("Goldbach's Conjecture:\n");
  printf("Every even integer is a sum of two odd primes.\n");
  printf("----------------------------------------------\n");
  printf("\n");
  printf("Beginning at: %d \n", BEGIN);
  printf("Ending at:    %d \n", END);


  /* A FOR loop calculates and prints out the results */ 

  for(number = BEGIN; number <= END; number++) {
    if (number % 2 == 0) {     /* Only even integers are examined */ 
      firstPrime = 3;
      lastPrime = number - firstPrime;
      /* Repeat until a sum of two odd primes that equals number has
	 been found */
      while ((isPrime(firstPrime) && isPrime(lastPrime)) == 0) {
	firstPrime += 2;
	lastPrime = number - firstPrime;
      } /* WHILE */
      printf("%10d = %9d + %9d \n", number, firstPrime, lastPrime); 
    } /* IF */
  } /* End of FOR loop */

  /* Terminate program */
  return status;    

} /* END OF MAIN */

See also Kurt Nørmarks solution.

 

	#include "primes.h"
	Before int main(void), we include the header file containing the function signature. The compiler thus knows the name of the function isPrime, the input argument type and the return type.

 

	for(number = BEGIN; number <= END; number++) {
	A FOR loop calculates and prints out the results. It runs for as long as the variable number is in the interval between the symbolic constants BEGIN and END.

 

	if (number % 2 == 0) { /* Only even integers are examined */
	Goldbachs conjecture deals with even integers, so we only bother to examine those. % is the modulo division operator.

 

	firstPrime = 3; lastPrime = number - firstPrime;
	firstPrime is set to the smallest odd prime number, and lastPrime is set such that the sum of firstPrime and lastPrime is equal to number.

 

	while ((isPrime(firstPrime) && isPrime(lastPrime)) == 0) {
	This WHILE loop is repeated until both firstPrime and lastPrime are prime numbers, i.e., two primes whose sum equals number have been found.

 

	firstPrime += 2; lastPrime = number - firstPrime; } /* WHILE */
	Inside the WHILE loop, the value of at least one of firstPrime and lastPrime is not a prime number. We therefore update firstPrime by two (next odd number), and lastPrime is set such that the sum of firstPrime and lastPrime is equal to number. Then they can be tested again.

 

	printf("%10d = %9d + %9d \n", number, firstPrime, lastPrime); } /* IF */ } /* End of FOR loop */
	The sum of the two prime numbers is printed out, and we can try again with a new number. This continues until number is greater than END.