Many new programmers soon find themselves with the task of having to write a pro- gram to generate a table of *prime numbers*. To refresh your memory, a positive integer *p *is a prime number if it is not evenly divisible by any other integers, other than 1 and itself. The first prime integer is defined to be 2. The next prime is 3, because it is not evenly divisible by any integers other than 1 and 3, and 4 is *not *prime because it *is *evenly divis- ible by 2.

There are several approaches that you can take to generate a table of prime numbers. If you have the task of generating all prime numbers up to 50, for example, the most straightforward (and simplest) algorithm to generate such a table is simply to test each integer *p *for divisibility by all integers from 2 through p–1. If any such integer evenly divided *p*, then *p *is not prime; otherwise, it is a prime number. Program 6.10 illustrates the program to generate a table of prime numbers.

Program 6.10 **Generating a Table of Prime Numbers**

// Program to generate a table of prime numbers

#include <stdio.h>

int main (void)

{

int p, d;

_Bool isPrime;

for ( p = 2; p <= 50; ++p ) {

isPrime = 1;

for ( d = 2; d < p; ++d )

if ( p % d == 0 )

isPrime = 0;

if ( isPrime != 0 )

printf (“%i “, p);

}

printf (“\n”);

return 0;

}

Program 6.10 **Output**

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Several points are worth noting about the program in Program 6.10. The outermost for statement sets up a loop to cycle through the integers 2 through 50. The loop variable p represents the value you are currently testing to see if it is prime. The first statement in the loop assigns the value 1 to the variable isPrime. The use of this variable will become apparent shortly.

A second loop is set up to divide p by the integers from 2 through p–1. Inside the loop, a test is made to see if the remainder of p divided by d is 0. If it is, you know that p cannot be prime because an integer other than 1 and itself can evenly divide it. To signal that p is no longer a candidate as a prime number, the value of the variable isPrime is set equal to 0.

When the innermost loop finishes execution, the value of isPrime is tested. If its value is not equal to zero, no integer was found that evenly divides p; therefore, p must be a prime number, and its value is displayed.

You might have noticed that the variable isPrime takes on either the value 0 or 1, and no other values. That’s why you declared it to be a _Bool variable. Its value is 1 as long as p still qualifies as a prime number. But as soon as a single even divisor is found, its value is set to 0 to indicate that p no longer satisfies the criteria for being prime. Often, variables that are used in such a manner are referred to as *flags*.A flag typically assumes only one of two different values. Furthermore, the value of a flag is usually test- ed at least once in the program to see if it is “on” (TRUE) or “off ” (FALSE), and some particular action is taken based upon the results of the test.

In C, the notion of a flag being TRUE or FALSE is most naturally translated into the values 1 and 0, respectively. So in the Program 6.10, when you set the value of isPrime to 1 inside the loop, you are effectively setting it as TRUE to indicate that p “is prime.”

If during the course of execution of the inner for loop an even divisor is found, the value of isPrime is set to FALSE to indicate that p no longer “is prime.”

It is no coincidence that the value 1 is typically used to represent the TRUE or “on” state and 0 to represent the FALSE or “off ” state. This representation corresponds to the notion of a single bit inside a computer. When the bit is “on,” its value is 1; when it is “off,” its value is 0. But in C, there is an even more convincing argument in favor of these logic values. It has to do with the way the C language treats the concept of TRUE and FALSE.

Recall from the beginning of this chapter that if the conditions specified inside the if statement are “satisfied,” the program statement that immediately follows executes. But what exactly does “satisfied” mean? In the C language, satisfied means nonzero, and nothing more. So the statement

if ( 100 )

printf (“This will always be printed.\n”);

results in execution of the printf statement because the condition in the if statement (in this case, simply the value 100) is nonzero and, therefore, is satisfied.

In each of the programs in this chapter, the notions of “nonzero means satisfied” and “zero means not satisfied” are used. This is because whenever a relational expression is evaluated in C, it is given the value 1 if the expression is satisfied and 0 if the expression is not satisfied. So evaluation of the statement

if ( number < 0 )

number = -number;

actually proceeds as follows:

- The relational expression number < 0 is evaluated. If the condition is satisfied, that is, if number is less than zero, the value of the expression is 1; otherwise, its value is 0.

- The if statement tests the result of the expression evaluation. If the result is nonzero, the statement that immediately follows is executed; otherwise, the state- ment is skipped.

The preceding discussion also applies to evaluation of conditions inside the for, while, and do statements. Evaluation of compound relational expressions such as in the statement

while ( char != ‘e’ && count != 80 )

also proceeds as outlined previously. If both specified conditions are valid, the result is 1; but if either condition is not valid, the result of the evaluation is 0. The results of the evaluation are then checked. If the result is 0, the while loop terminates; otherwise it continues.

Returning to Program 6.10 and the notion of flags, it is perfectly valid in C to test if the value of a flag is TRUE by an expression such as

if ( isPrime )

rather than with the equivalent expression

if ( isPrime != 0 )

To easily test if the value of a flag is FALSE, you can use the *logical negation *operator, !. In the expression

if ( ! isPrime )

the logical negation operator is used to test if the value of isPrime is FALSE (read this statement as “if not isPrime”). In general, an expression such as

! *expression*

negates the logical value of *expression*. So if *expression *is zero, the logical negation operator produces a 1. And if the result of the evaluation of *expression *is nonzero, the negation operator yields a 0.

The logical negation operator can be used to easily “flip” the value of a flag, such as in the expression

myMove = ! myMove;

As you might expect, this operator has the same precedence as the unary minus opera- tor, which means that it has higher precedence than all binary arithmetic operators and all relational operators. So to test if the value of a variable x is not less than the value of a variable y, such as in

! ( x < y )

the parentheses are required to ensure proper evaluation of the expression. Of course, you could have equivalently expressed the previous expression as

x >= y

In Chapter 4, “Variables, Data Types, and Arithmetic Expressions,” you learned about some special values that are defined in the language which you can use when working with Boolean values. These are the type bool, and the values true and false. To use these, you need to include the header file <stdbool.h> inside your program. Program 6.10A is a rewrite of Program 6.10, which takes advantage of this data type and values.

Program 6.10A **Revising the Program to Generate a Table of Prime Numbers**

// Program to generate a table of prime numbers

#include <stdio.h>

#include <stdbool.h>

int main (void)

{

int p, d;

bool isPrime;

for ( p = 2; p <= 50; ++p ) {

isPrime = true;

for ( d = 2; d < p; ++d )

if ( p % d == 0 )

isPrime = false;

if ( isPrime != false )

printf (“%i “, p);

}

printf (“\n”);

return 0;

}

Program 6.10A **Output**

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

As you can see, by including <stdbool.h> in your program, you can declare variables to be of type bool instead of _Bool. This is strictly for cosmetic purposes because the for- mer is easier to read and type than the latter, and it fits in more with the style of the other basic C data types, such as int, float, and char.

Source: Kochan Stephen G. (2004), *Programming in C: A Complete Introduction to the C Programming Language*, Sams; Subsequent edition.