最大公约数和最小公倍数的三种超简单算法
1、辗转相除法：取两个数中最大的数做除数，较小的数做被除数，用最大的数除较小数，如果余数为0，则较小数为这两个数的最大公约数，如果余数不为0，用较小数除上一步计算出的余数，直到余数为0，则这两个数的最大公约数为上一步的余数。
如下示例程序:
#include<stdio.h>
int main()
{
int x, y, z, m, n;
printf("请输入两个数：");
scanf_s("%d%d", &x, &y);
m = x, n = y;
while (y != 0)
{
z = x%y;
x = y;
y = z;
}
printf("最大公约数是: %d\n", x);
printf("最小公倍数是: %d\n", m*n / x);
system("pause");
return 0;
}
2、相减法：取两个数中的最大的数做减数，较小的数做被减数，用最大的数减去小数，如果结果为0，则被减数就是这两个数的最大公约数，如果结果不为0，则继续用这两个数中最大的数减较小的数，直到结果为0，则最大公约数为被减数。
如下示例程序:
#include<stdio.h>
int main()
{
int x, y, m, n;
printf("请输入两个数：");
scanf_s("%d%d", &x, &y);
m = x, n = y;
while (x!=y)
{
if (x>y)
x = x-y;
else
y = y-x;
}
printf("最大公约数是: %d\n", x);
printf("最小公倍数是: %d\n", m*n / x);
system("pause");
return 0;
}
3、穷举法：将两个数作比较，取较小的数，以这个数为被除数分别和输入的两个数做除法运算，被除数每做一次除法运算，值减少1，直到两个运算的余数都为0，则该被除数为这两个数的最大公约数。
如下示例程序:
#include<stdio.h>
int main()
{
int x, y, i, m, n;
printf("请输入两个数：");
scanf_s("%d%d", &x, &y);
m = x, n = y;
for (i = 1; i <= x; i++)
{
if (x%i == 0 && y%i == 0)
}
for (i = x; i > 0; i--)
{
if (x%i == 0 && y%i == 0)
}
printf("最大公约数是: %d\n", i);
printf("最小公倍数是: %d\n", m*n / i);
system("pause");
return 0;
}