Consider the following code which determines whether x and y are relatively prime (that is, there are
Fantastic news! We've Found the answer you've been seeking!
Question:
Consider the following code which determines whether x and y are relatively prime (that is, there are no integers ≥ 2 that divide evenly into both x and y):
bool IsRelativelyPrime(int x, int y) {
for (int i = 2; i <= x && i <= y; i++) {
if ((x % i == 0) && (y % i == 0)) return false;
}
return true;
}
You may assume that x and y are both at least 2.
Identify the loop invariant for the above code, prove the correctness of your invariant using induction, and then use the loop invariant to prove the correctness of the algorithm.
Related Book For
Probability and Stochastic Processes A Friendly Introduction for Electrical and Computer Engineers
ISBN: 978-1118324561
3rd edition
Authors: Roy D. Yates, David J. Goodman
Posted Date: