兄弟连地狱公路兔子洞:如何求最大公约数？

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

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

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

定义：如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。例： 在2、4、6中，2就是2，4，6的最大公约数。
最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。

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

两个数的最大公约数是整数,其值应不大于两个数中的小的那个数，应不小于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)；

大数。整除时的除数就是最大公约数。举例：
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

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