Previous: 2.5.5 Controlling Loop Termination
Up: 2.5 More C Statements
Previous Page: 2.5.5 Controlling Loop Termination

2.5.6 More Complex Loop Constructs - Nested Loops

As we mentioned above, the <statement> that is the body of the loop can be any valid C statement and very often it is a compound statement. This includes a while statement, or a while statement with the block. Such a situation is called a nested loop. Nested loops frequently occur when several items in a sequence are to be tested for some property, and this testing itself requires repeated testing with several other items in sequence. To illustrate such a process, consider the following task:

Task

Find all prime numbers less than some maximum value.

The problem statement here is very simple; however, the algorithm may not be immediately obvious. We must first understand the problem.

A prime number is a natural number, i.e. 1, 2, 3, 4, etc., that is not exactly divisible by any other natural number, except 1 and itself. The number 1 is a prime by the above definition. The algorithm must find the other primes up to some maximum. One way to perform this task is to use a process called generate and test. In our algorithm, we will generate all positive integers in the range from 2 to a maximum (constant) value PRIME_LIM. Each generated integer becomes a candidate for a prime number and must be tested to see if it is indeed prime. The test proceeds as follows: divide the candidate by every integer in sequence from 2 up to, but not including itself. If the candidate is not divisible by any of the integers, it is a prime number; otherwise it is not.

The above approach involves two phases: one generates candidates and the other tests each candidate for a particular property. The generate phase suggests a loop, each iteration of which performs the test phase, which is also a loop; thus we have a nested loop. Here is the algorithm.

set the candidate to 2
     while (candidate < PRIME_LIM) {
          test the candidate for prime property
          print the result if a prime number
          generate the next candidate
     }

In testing for the prime property, we will first assume that the candidate is prime. We will then divide the candidate by integers in sequence. If it is divisible by any of the integers excluding itself, then the candidate is not prime and we may generate the next candidate. Otherwise, we print the number as prime and generate the next candidate.

We need to keep track of the state of a candidate: it is prime or it is not prime. We can use a variable, let's call it prime which will hold one of two values indicating True or False Such a state variable is often called a flag. For each candidate, prime will be initially set to True. If the candidate is found to be divisible by one of the test integers, prime will be changed to False. When testing is terminated, if prime is still True, then the candidate is indeed a prime number and can be printed. This testing process can be written in the following algorithm:

set prime flag to True to assume candidate is a prime
     set test divisor to 2
     while (test divisor < candidate) {
          if remainder of (candidate/test divisor) == 0
               candidate is not prime
          get the next test divisor in sequence
     }

We will use the modulus (mod) operator, % described earlier, to determine the remainder of (candidate / divisor). Here is the code fragment for the above algorithm:

prime = TRUE;
     divisor = 2;
     while (divisor < candidate)  {
          if ((candidate % divisor) == 0)
               prime = FALSE;

          divisor = divisor + 1;
     }

The program follows the algorithm step by step. We have defined symbols TRUE and FALSE to be 1 and 0, respectively. The final if statement uses the expression (prime) instead of (prime == TRUE); the result is the same. The expression (prime) is True (non-zero) if prime is TRUE, and False (zero) if prime is FALSE. Of course, we could have written the if expression as (prime == TRUE), but it is clear, and maybe more readable, as written.

We have included a debug statement in the inner loop to display the values of candidate, divisor, and prime. Once the we are satisfied that the program works correctly, the debug statement can be removed.

Here is a sample session with the debug statement and PRIME_LIM set to 8:

***Prime Numbers Less than 8***

     1 is a prime number
     2 is a prime number
     debug: candidate = 3, divisor = 2 prime = 1
     3 is a prime number
     debug: candidate = 4, divisor = 2 prime = 1
     debug: candidate = 4, divisor = 3 prime = 0
     debug: candidate = 5, divisor = 2 prime = 1
     debug: candidate = 5, divisor = 3 prime = 1
     debug: candidate = 5, divisor = 4 prime = 1
     5 is a prime number
     debug: candidate = 6, divisor = 2 prime = 1
     debug: candidate = 6, divisor = 3 prime = 0
     debug: candidate = 6, divisor = 4 prime = 0
     debug: candidate = 6, divisor = 5 prime = 0
     debug: candidate = 7, divisor = 2 prime = 1
     debug: candidate = 7, divisor = 3 prime = 1
     debug: candidate = 7, divisor = 4 prime = 1
     debug: candidate = 7, divisor = 5 prime = 1
     debug: candidate = 7, divisor = 6 prime = 1
     7 is a prime number

***Prime Numbers Less than 20***

     1 is a prime number
     2 is a prime number
     3 is a prime number
     5 is a prime number
     7 is a prime number
     11 is a prime number
     13 is a prime number
     17 is a prime number
     19 is a prime number

In looking at the debug output, you might see that the loop that tests for the prime property of a candidate is not an efficient one. For example, when candidate is 6, we know that it is not prime immediately after divisor 2 is tested. We could terminate the test loop as soon as prime becomes false (if it ever does). In addition, it turns out that a candidate needs to be tested for an even more limited range of divisors. The range of divisors need not exceed the square root of the candidate. (See Problem 6 at the end of the chapter).