Exercise 4-12 - CBD page 166 - Kurt Nørmark (inefficient).

#include "primes.h"

int primeNumber(int i);

int main(void){

  int numPrimes, i;
 
  printf("V2: Primes will be printed\n");
  printf("----------------------\n\n");
  printf("How many do you want to see? ");
  scanf("%d",&numPrimes);

  for(i = 1; i <= numPrimes; i++)
    printf("%6d:  %10d\n", i, primeNumber(i));

  return 0;
}

/* Find and return the i'th prime number */
int primeNumber(int i){
  int firstPrime = 2, pnum = 1, candidate = firstPrime;
  while (pnum < i){
    candidate++;
    if (is_prime(candidate)) pnum++;
  }
  return candidate;
}

There are three different solutions to this exercise. The original one made by Jan Dimon. This one, which from a problem solving point of view is straightforward, but very inefficient. And a better one, which I recommend.

 

	for(i = 1; i <= numPrimes; i++) printf("%6d: %10d\n", i, primeNumber(i));
	This is a very simple for loop which will print numPrimes. It uses the function primeNumber(i), which calculates prime number i.

 

/* Find and return the i'th prime number */ int primeNumber(int i){ int firstPrime = 2, pnum = 1, candidate = firstPrime; while (pnum < i){ candidate++; if (is_prime(candidate)) pnum++; } return candidate; }

This is the function which calcultes the i'th prime number. In the while loop we increment pnum each time we encounter a prime number. We use the boolean function is_prime for this purpose. Notice that this function, is_prime, was given to us in the exercise formulation. It is crucial to notice that pnum is only incremented when candidate is a prime number. Therefore we know that candiate is a prime number when the while loop exits.

 

This program is not efficient. We call primeNumber(i) many times. In each call we repeatedly find the first i - 1 prime numbers. To make things even worse, the given boolean function is_prime(x) is also very inefficient either. The alternative solution avoids the repeated computation of prime numbers.

 

A practical remark about compilation of the example. First compile is_prime.c with gcc -c is_prime.c . Then make a header file primes.h. Now compile the dissected program by gcc primes-main.c is_prime.o, where we assume that the program is located in the C source file primes-main.c.