求两个数的最大公约数

第一种方法：概念法

若两个数有最大公约数那么该数肯定大于等于1小于等于两个数中较小的数

那么取两个数中较小的数赋值给变量min

所以，若min大于等于1则执行循环

如果两个数a和b都和min取模且都等于0那么说明min就是两个数的最大公约数

那么直接break跳出循环

如果不满足条件那么min自减直到达到条件

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable :4996)
int main()
{
int a, b;
printf("输入a和b的值");
scanf("%d %d", &a, &b);
int min = a > b ? b : a;
while (min >= 1)
{
if (a%min == 0 && b%min == 0)
{
break;
}
min--;
}
printf("最大公约数为：%d\n", min);
system("pause");
return 0;

}

第二种方法：辗转相减法

要使用这种方法首先我们得明确一个概念

假如两个数a和b的最大公约数为t

那么久说明a和b都可以由若干个t相加得到

那么a和b的差值也可以由若干个t相加得到

如果一直相减直到相减得到的数相等时该数就是最大公约数

此方法相比上个方法大大提高了运行效率

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable :4996)
int main()
{
int a, b;
printf("输入a和b的值");
scanf("%d %d", &a, &b);
while (1)
{
if (a > b)
{
a -= b;
}
else if (b > a)
{
b -= a;
}
else
{
break;
}
}
printf("最大公约数为：%d\n", a);
system("pause");
return 0;

}

运行结果如图：

第三种方法：辗转相除法

同样的，在用此方法时我们得明白一个道理

假设a和b的最大公约数为t

那么a和b肯定都能被t整除

那么a和b的线性组合（ma+-nb)也肯定能被t整除（m和n可以取任意整数）

如果a>b,假设 a/b=n 余 c，可以表示为 a=nb+c 也可以表示为 a-nb=c 

可以得出余数c也可以被最大公约数t整除！！！

所以将a与b取模得到的余数赋值给较大的数与另外一个数取模

直到余数为0

那么旧说明得到了最大公约数

因为我们将a和b取模得到的余数赋值给了较大的数

而且余数为0时循环结束

所以控制循环的语句应该为a*b！=0

得到的最大公约数为a和b中非零的值。

#include<stdio.h>

#include<stdlib.h>
#pragma warning(disable :4996)
int main()
{
int a, b;
printf("输入a和b的值");
scanf("%d %d", &a, &b);
while (a*b != 0)
{
if (a > b)
{
a %= b;
}
else
{
b %= a;
}
}
int c = a == 0 ? b : a;
printf("最大公约数为：%d\n", c);
system("pause");
return 0;

}

运行结果如图：