目录
一.求最大公约数
1.枚举法求最大公约数
2.辗转相除法
二.求最小公倍数
1.枚举法求最小公倍数
2.简易法
3.公式法
一.求最大公约数
1.枚举法求最大公约数
思路：先求两个数中的最小值，最大公约数不可能大于两个数的最小数
比如6和18，最大公约数就是6
再如3和9，最大公约数就是3
然后再从1开始循环遍历到最小值的数中找最大公约数即可，因为1是最小的因子了，0不能作为除数
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
int ret = 0;
scanf("%d %d", &a, &b);
int min = a < b ? a : b;
for (int i = 1; i <= min; i++)
{
if (a % i == 0 && b % i == 0)
{
ret = i;
}
}
printf("最大公约数是%d\n", ret);
return 0;
}2.辗转相除法
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
while (b)
{
int t = a % b;
a = b;
b = t;
//比如a=12，b=18 第一次t=12 a=18 b=12.第二次t=6 a=12 b=6 第三次t=0 a=6 b=0循环终止，所以最大公约数是6
}
printf("最大公约数是%d\n", a);
return 0;
}二.求最小公倍数
1.枚举法求最小公倍数
思路：求两个数中的最大值，因为最小公倍数肯定 >= 两个数中的最大值
那比如6和12，最小公倍数就是12了
再如5和10，最小公倍数就是10了
值得注意的是他与最大公约数有所不同，最大公约数是遍历到两个数的“最小值”，而最小公倍数是从两个数中的最大值开始遍历，最小公倍数只要找到一个满足条件的公倍数，立马结束循环，（如果不符合条件再++即可）因为你要求的是最小的公倍数
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int max = a > b ? a : b;
while (1)
{
if (max % a == 0 && max % b == 0)
break;
//一旦找到满足条件的因子就跳出循环
//因为这里求的是最小公倍数
else max++;
}
printf("最小公倍数是%d\n", max);
return 0;
}
2.简易法
因为最小公倍数应该为两个数共同的倍数，所以我们可以用其中的第一个数的整数倍对第二个数整除，如果第一个数的整数倍也能整除第二个数，说明第一个数的整数倍就是两个数共同的倍数，那么找到这一个了(第一次找到的公倍数)就是最小公倍数了，那么break跳出循环即可文章来源：https://www.toymoban.com/news/detail-716685.html
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int i = 0;
for (i = 1; ; i++)
{//i=1，2...表示a的几倍，保证了是a的倍数， a*i就可以表示为最小公倍数
if (a * i % b == 0)
{
printf("%d\n", a * i);
break;
}
}
return 0;
}3.公式法
用已知最大公约数求最小公倍数就可以，已知两个数a，b，最大公约数是c，则最小公倍数是a*b / c，即先求出最大公约数，两个数相乘再除以最大公约数即最小公倍数文章来源地址https://www.toymoban.com/news/detail-716685.html
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
//保存a和b值，因为下面求最小公倍数用到a和b
int tmpa = a, tmpb = b;
while (b)
{
int t = a % b;
a = b;
b = t;
}
//此时tmpa和tmpb才是原来的值，a已经为最大公约数
printf("最小公倍数是%d\n", tmpa * tmpb / a);
return 0;
}到了这里，关于【c语言】—求最大公约数和最小公倍数多种方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
