输入两个正整数 m 和 n, 求其最大公约数和最小公倍数. 

<1> 

 

用辗转相除法求最大公约数

算法描述: 
m 对 n 求余为 a, 若 a 不等于 0 

 

则 m <- n, n <- a, 

 

继续求余

 

否则 n 

 

为最大公约数

<2> 

 

最小公倍数 = 

 

两个数的积 / 

 

最大公约数

#include 
int main() 
{ 
int m, n; 
int m_cup, n_cup, res; /*被除数, 除数, 余数*/ 
printf("Enter two integer:\n"); 
scanf("%d %d", &m, &n); 
if (m > 0 && n >0) 
{ 
m_cup = m; 
n_cup = n; 
res = m_cup % n_cup; 
while (res != 0) 
{ 
m_cup = n_cup; 
n_cup = res; 
res = m_cup % n_cup; 
} 
printf("Greatest common divisor: %d\n", n_cup); 
printf("Lease common multiple : %d\n", m * n / n_cup); 
} 
else printf("Error!\n"); 
return 0; 
} 

 

★ 关于辗转相除法, 搜了一下, 在我国古代的《九章算术》中就有记载，现摘录如下: 

“

约分术曰： 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等

” 

也。以等数约之。

“

”

“

”

“

”

其中所说的 等数 ，就是最大公约数。求 等数 的办法是 更相减损 法，实际上就是辗转

 

相除法。

 

辗转相除法求最大公约数，是一种比较好的方法，比较快。