Discrete Mathematics for Computer Science

76 CHAPTER 1 Sets, Proof Templates, and Induction

the value N/2k, where 2 k is the highest power of 2 that is a factor of N, will be evaluated

as FALSE, because the value tested is odd. In this case, the process terminates by printing

the final value of N/2k. For example, if N = 78, the condition Mod(78, 2) = 0 is TRUE

and N is replaced by 78/2 = 39. Now, when the condition Mod(39, 2) = 0 is tested, the

condition is FALSE. The while loop is exited, and the value of N/2 = 39 is printed.

Theorem 3. Prove that the Largest Odd Divisor algorithm is correct.

Proof Exercise for the reader. 0

Factorization

Often, a small insight that does not seem particularly significant can make a big difference

in developing an algorithm. In the code for PrintFactors, the idea is that if an integer n can

be factored as j • k where 1 < j, k < n, then either j or k is in the range I to n-n. To find

a factor of n, we can focus on finding a value between 2 and In rather than a value from

2ton - 1.

INPUT: Integer N > I

OUTPUT-: Factors of N

PrintFactors (N) /* Initial call */

PrintFactors (n) /* The recursive procedure *!

RootN =

TrialFactor = [RootNj

while (mod(n, TrialFactor) :A 0) do

/* If TrialFactor is a divisor of n, the loop

will be executed zero times. */

TrialFactor = TrialFactor - 1

if (TrialFactor < 1) then

print n

else

PrintFactors(TrialFactor)

PrintFactors(n/TrialFactor)

The procedure PrintFactors is designed to display the factors of any integer. For

example, we know that the factors of 12 are 2, 2, and 3. The value of RootN is ini-

tially assigned the value L,/2] = 3. Therefore, the first time through PrintFactors, we

set TrialFactor equal to 3, and we test Mod(n, TrialFactor) 0 0. The condition is FALSE,

which means that 3 is a factor of n. TrialFactor is greater than 1, so we call PrintFactors(3)

and PrintFactors(12/3). PrintFactors(3) prints the factor 3. PrintFactors(4) starts by set-