Exercise 4-15 - CBD page 168 - Kurt Nørmark's solution

Solution index Textual C program

#include <stdio.h>
#include "primes.h"

#define BEGIN 1000000
#define END   2000000

int even (int);
int odd (int);

void test_goldbachs_conjecture(int i){
  int j;
  for(j = 3; j <= i/2; j += 2)
    if (is_prime(j) && is_prime(i-j) && odd(j) && odd(i-j)){
      printf("%d = %d + %d\n", i, j, i-j);
      return;
    }
  printf("%d is not composable\n", i);
}

int main(void) {
  int i, start;

  start = even(BEGIN)? BEGIN : BEGIN + 1;
  for(i = start; i <= END; i += 2)
    test_goldbachs_conjecture(i);
    
  return 0;
}

int even(int i){
  return i%2 == 0;
}

int odd(int i){
  return !(even(i));
}

int main(void) {
  int i, start;

  start = even(BEGIN)? BEGIN : BEGIN + 1;
  for(i = start; i <= END; i += 2)
    test_goldbachs_conjecture(i);
    
  return 0;
}

With this program I want to give an alternative solution to Jan Dimon's solution. The main difference is that I do not want to rely on two nested loops in the main program. Rather, I use a single for loop which traverses even number. The assignment of start uses a conditional expression to ensure that the value of start is even at the beginning of the for loop. We outsource the main portion of the problem solving to the function test_goldbachs_conjecture. Overall, this is a better solution because we have broken the original problem, as stated in the exercise, into two subproblems: The iteration in main, and the test of the conjecture in test_goldbachs_conjecture. In general, this is the way we control the complexity of non-trivial programs!

void test_goldbachs_conjecture(int i){
  int j;
  for(j = 3; j <= i/2; j += 2)
    if (is_prime(j) && is_prime(i-j) && odd(j) && odd(i-j)){
      printf("%d = %d + %d\n", i, j, i-j);
      return;
    }
  printf("%d is not composable\n", i);
}

We prove the conjecture for the integer i by splitting i into the sum j + (i - j). The local variable j runs from 3 to i/2, through only odd numbers.

  for(j = 3; j <= i/2; j += 2)
    if (is_prime(j) && is_prime(i-j) && odd(j) && odd(i-j)){
      printf("%d = %d + %d\n", i, j, i-j);
      return;
    }
  printf("%d is not composable\n", i);

Inside the for loop we test j and j-i for primality and for oddness. The prime test is essential, but the oddness test is not strictly necessary, because the enclosing for loop ensures that we only touch odd numbers, j and i-j. However, with respect to this detail we chose a conservative approach. If we encounter numbers j and i-j for which the conditions hold we print them out, and we return immediately from the function. Only a single case is reported for each even number passed to test_goldbachs_conjecture. If the for loop terminates, we have found a counter example, and this is reported in the final printf statement. Notice again, that we do not expect the for loop to terminate normally. If it did, Goldbachs conjecture would not hold!

Generated: Wednesday, March 29, 2006, 12:33:23
This program dissection page is generated from an XML-in-LAML source file