现在的位置: 首页 > 自动控制 > 工业·编程 > 正文

求两数的最大公约数

2012-07-30 06:20 工业·编程 ⁄ 共 219字 ⁄ 字号 暂无评论

算法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;
}

给我留言

留言无头像?