题目
输入两个整数,求这两个数的最大公约数和最小公倍数。
我们先来讲最大公约数
第一种求法(辗转相除法)这个方法代码较洁简,我也比较推荐就是刚开始有点比较难了解。
首先,来看看怎么求最大公约数,求最大公约数需要用到欧几里得算法,也称为辗转相除法。算法就是用两数中较大的数a除以另一个数b得出余数c,然后判断c是否为0(意思a能够整除b),为0则b为最大公因数;反之,则把b作为a,c作为b,继续上面的操作,直至余数为0.
翻译一下,用个简单的代码输入输出解释一下:
输入18 24 (这里本来要比较两数的大小,然后直接公式得到,但也可以省去比大小,用循环)
第一次循环
a = 18 b = 24 c = a%b = 18%24 = 18
然后将a=b b=c (结合第二次循环,可以得出我们不需要比大小,第一次小除大,会两值不会变,但位置反,可以直接用)
a = 24 b=18
第二次循环
a = 24 b = 18 c = a%b = 24%18 = 6
然后将结果a = b b =c
a =18 b=6 (可以静下心来感受一下这里面值相对大小的改变)
第三次循环
a = 18 b = 6 c = a%b = 18%6 = 0
c的结果等于0时循环结束。
代码如下
#include <stdio.h>
int main()
{
int m = 0;
int n = 0;
int temp = 0;
scanf("%d %d", &m, &n);//两个整数while (tmp = m % n)//循环,大小不对,自动换位置。
{
m = n;
n = temp;
}
printf("最大公约数为:%d\n", n);
return 0;
}
还有一个最直接的办法,将所有的情况都举出来。
思路:
两种情况讨论
1.如果大数可以整除小数,那么最大公约数为小数。
2.如果不能整除小数,那就找一个比较大,但时小于较小的数,能被两数同时整除的数。
代码如下:
#include<stdio.h>
int main(){
int a = 0;
int b = 0;
printf("请输入两个整数:");
scanf("%d%d", &a, &b);
if (a >= b){
int i = 0;
for (i = b; i >= 1; i--){
if (a%i == 0 && b%i == 0){
printf("最大公约数为:%d\n", i);
break;
}
}
}
else{
int j = 0;
for (j = a; j >= 1; j--){
if (a%j == 0 && b%j == 0){
printf("最大公约数为:%d\n", j);
break;
}
}
}
return 0;
}
求完最大公约数,接下来求最小公倍数
根据公式法,我们可以知道两数a和b的乘积等于它们的最大公约数和最小公倍数的积,所以最小公倍数可以通过最大公约数来求。
因为上面已经求完最大公约数,所以可以直接用两数相乘然后除最大公约数
代码如下
#include<stdio.h>
int main()
{
int a, b, c, d;
scanf("%d %d %d", &a, &b,%c);//a,b为数,c为最大公约数;
d = a * b / c;
printf("%d",c);
} 文章来源:https://www.toymoban.com/news/detail-440393.html
谢谢大家的观看! 文章来源地址https://www.toymoban.com/news/detail-440393.html
到了这里,关于【C语言】两个整数最大公约数和最小公倍数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!