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

#include "primes.h"

int next_prime_after(int prime);

int main(void){

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

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

  return 0;
}

/* Given that prime is a prime number return the smallest prime which
   is larger than prime */
int next_prime_after(int prime){
  int candidate = (prime == 2)? 3 : prime + 2;
  while (!is_prime(candidate)) candidate += 2; 
  return candidate;
}  

There are three different solutions to this exercise. The original one made by Jan Dimon. This one and another one, which is very inefficient due to repeated calculation of prime numbers.

 

	for(i = 1, prime = 2; i <= numPrimes; i++, prime = next_prime_after(prime)) printf("%6d: %10d\n", i, prime);
	This for loop runs numPrimes times, and in each iteration we call the function next_prime_after(p), which finds the next prime number after p.

 

	/* Given that prime is a prime number return the smallest prime which is larger than prime */ int next_prime_after(int prime){ int candidate = (prime == 2)? 3 : prime + 2; while (!is_prime(candidate)) candidate += 2; return candidate; }
	This is the function which calcultes the smallest prime number, which is larger than the parameter prime. Because all prime numbers, apart from 2, is odd, we can increment candidate with 2. Notice, however, the calculation of the initial candidate, namely 3 which follows 2. This becomes a special case. Again we use the function is_prime which was given in the exercise text.

 

This program is more efficient than the alternative solution. For illustration of this, run this program and the other program, and fell the difference yourself. The reason is that we take an existing prime as the starting point, and from this prime number we find the next one. Thus, there is no repeated calculation of the all the smaller prime numbers. With this solution the for loop in main becomes slightly more complicate, but this extra complication is well worth the saving in execution time.

 

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.