算法E:(欧几里得算法)
给定两个正整数m和n,求它们的最大公因子,即能够同时整除m和n的最大的正整数。
E1:(求余数)以n除m并令r为所得余数(我们将有0<=r<n)。
E2:(余数为0?)若r=0,算法结束;n即为答案。
E3:(互换)置m<---n , n<---r ,并返回步骤 E1。
对应实现函数:
int greatestCommonDivisor(int m,int n)
{
int r;
while(r=m%n){
m=n;
n=r;
}
return n;
}