Calculating Greatest Common Divisor using While loop

Question

Dylan 2024-4-23

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2110876-calculating-greatest-common-divisor-using-while-loop

回答： Lokesh 2024-4-23

Instead of using built in 'GCD' function, I am to devise code to calculate the GCD of two numbers using a while loop. I cannot figure out how to code it. Requesting some help!

%% Input two numbers.
% There is no error checking so put in positive integers of bad things may
% happen - MC
x = input('Enter an integer > 0: ');
y = input('Enter another integer > 0: ');
if x >= y
    numerator = x;
    denominator = y;
else
    numerator = y;
    denominator = x;
end
%% Calculates the GCD
% ------------ Replace this piece of the code with a while loop -----------
r = rem(numerator, denominator);
while r > 0
    if r == 0
        GCD = denominator;
        break;
    end
end
fprintf('The GCD of %d and %d is %d: it took calculations\n',x,y,GCD)

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Voss 2024-4-23

Here are some references that may help:

https://sites.math.rutgers.edu/~greenfie/gs2004/euclid.html

https://en.wikipedia.org/wiki/Euclidean_algorithm#Description

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Lokesh 2024-4-23

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2110876-calculating-greatest-common-divisor-using-while-loop#answer_1446701

在 MATLAB Online 中打开

Hi Dylan,

I understand that you are working on implementing the GCD of two numbers using a while loop, aiming to apply the Euclidean algorithm.

To ensure the algorithm functions as intended, it is crucial to update the values being used to calculate the remainder within each iteration of the loop.This process involves treating the current denominator as the new numerator and the current remainder as the new denominator, then recalculating the remainder for the next iteration. This cycle continues until the remainder is zero, at which point the last non-zero denominator is the GCD.

Here is how you can modify your loop to correctly implement the algorithm:

%% Calculates the GCD
r = rem(numerator, denominator); % Initial remainder
while r > 0
    numerator = denominator; % The previous denominator becomes the new numerator
    denominator = r; % The remainder becomes the new denominator
    r = rem(numerator, denominator); % Calculate the new remainder
end
GCD = denominator; % The last non-zero remainder
fprintf('The GCD of %d and %d is %d.\n', x, y, GCD);