Consider the Prolog gcd program in Figure 1.2. Does this program work “backward” as well as forward? (Given integers d and n, can you use it to generate a sequence of integers m such that gcd(n, m) = d?) Explain your answer.

Figure 1.2:

Transcribed Image Text:

int gcd(int a, int b) { // C while (a != b) { if (a > b) a = a - b; else b = b - a; return a; (* OCaml *) let rec gcd a b = if a = b then a else if a > b then gcd b (a - b) else gcd a (b a) gcd (A, B,G) :- A = B, gcd (A,B,G) :- A > B, C is A-B, gcd(C,B,G). gcd (A,B,G) :- B > A, C is B-A, gcd(C,A,G). G = A. % Prolog %3D