如何求最大公约数？

Question

想问最大公约数的定义和公式，谢谢。

Answer 1

求两个数的最大公约数的方法

（1）用短除法求两个数的最大公约数，一般先用这两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来，在除的过程中，有时也可以用两个数的公约数去除。

（2）求两个数的最大公约数的两种特殊情况：①如果这两个数存在着倍数关系（即较大数是较小数的倍数），那么，较小数就是这两个数的最大公约数；②如果两个数是互质数，那么它们的最大公约数就是1。

Answer 2

求两个数的最大公约数的方法

两个数的最大公约数是整数,其值应不大于两个数中的小的那个数，应不小于1。

公约数即能除尽给定的那两个数的整数，余数为0。

最大公约数是公约数中最大的那个数。

程序设计：
（1）比较已给两数大小，选出小的
int x,y
if (x > y ) 则y小
（2）循环语句
for (i=小的那个数;i>=1;i--)
如果i能整除两者则输出结果。
if （ (x/i*i== x) && (y/i*i == y)) break;
printf("最大公约数是 %d\n",i)；

Answer 3

大数。整除时的除数就是最大公约数。举例：
222 407求最大公约数：
222 407（407除以222余数185)
222 185(222除以185余数37)
37 185（185除以37余数0）
所以最大公约数为37
39 24求最大公约数
39 24（39/24，余数15）
15 24（24/15，余数9）
15 9（15/9，余数6）
6 9（9/6，余数3）
6 3（6/3，余数0)
所以最大公约数为3本回答被网友采纳

Answer 4

int t,r;
if(v>u)
{
t=u;u=v;v=t;
}
while((r=u%v)!=0)
{
u=v;v=r;
}
return(v)

Answer 5