Boolean Flags

If your code to detect if a number is prime passed all tests on the previous page, you probably wrote something similar to this:

int prime = 1;
int i;

i = 2;
while (i * i <= n) {
	if (n % i == 0) {
		prime = 0;
		break;
	}
	++i;
}

The prime variable here is a flag: a boolean variable (accepts values of 1 for "true" and 0 for "false") which we use to check if multiple conditions are all satisfied, or if at least one of them fails.

You might use a flag if you want to answer this question: "is the condition true for all elements of some set I care about?" In the prime number exercise above, the condition is "the number n is not divisible by any number i less than n", and to check it, we first assume that it is true by setting prime = 1, and then check the condition for each number i, and if we find one that does not satisfy the condition, we reset the prime flag to 0. At this point, there is no need to check further, so we break; from the loop.

One fun thing about this specific example is that it is totally possible to write this code without using an extra flag variable. Consider this:

int i;

i = 2;
while (i * i <= n) {
	if (n % i == 0) {
		break;
	}
	++i;
}  

/* you are here: is n prime or composite? */

At the "you are here" point, can we figure out if n is prime or not without having the prime flag?

Indeed, we can: if i * i > n after the loop, it means that we exited the loop after checking all possible values of i, which guarantees that n is prime. If i * i <= n after the loop, it means we exited using break;, which means n is composite.

Even though it's easy to avoid using the boolean flag in this specific case (and in many other cases), using the explicit flag often makes the code easier to write, and easier to understand.

With that, let's move on and learn about one more type of the loops–the for loops!