Assume that p and q are non-zero positive integers. What does the following…
2022
Assume that p and q are non-zero positive integers. What does the following program segment compute?
while (p != q)
{
if (p > q)
p = p - q;
else
q = q - p;
}
printf("%d", p);Answer: B. Compute the GCD of the given numbers — ConceptThe subtraction form of the Euclidean algorithm preserves the greatest common divisor: if a > b, then gcd(a, b) = gcd(a - b, b), and similarly when b >…
- A.
Subtract the smaller number from the larger number
- B.
Compute the GCD of the given numbers
- C.
Compute the LCM of the given numbers
- D.
Run indefinitely
Attempted by 393 students.
Show answer & explanation
Correct answer: B
Concept
The subtraction form of the Euclidean algorithm preserves the greatest common divisor: if a > b, then gcd(a, b) = gcd(a - b, b), and similarly when b > a.
For positive integers, repeatedly reducing the larger value must eventually make the two values equal. Their common value is the GCD of the original inputs.
Application
Take p = 18 and q = 12. Since p > q, the first update gives (p, q) = (6, 12).
Now q > p, so q becomes 12 - 6 = 6, giving (p, q) = (6, 6).
The condition p != q is now false, so the loop stops and printf outputs 6.
Cross-check
The common divisors of 18 and 12 are 1, 2, 3, and 6; the greatest is 6, which matches the traced output. Therefore, the program computes the GCD of the given numbers.