最大公约数与最小公倍数
最大公约数与最小公倍数
1.题目描述
输入两个正整数m和n，求其最大公约数和最小公倍数。
2.格式与样例
输入格式
输入两个整数，以空格隔开。
输出格式
最大公约数和最小公倍数，各占一行
输入样例
16 8
输出样例
8
16
3.参考答案
#include"stdio.h"
int gcd(int a,int b);//函数声明
int lcm(int a,int b);//函数声明
int main()
{
int a,b;
scanf("%d %d",&a,&b);
printf("%d %d",gcd(a,b),lcm(a,b));
return ;
}
int gcd(int a,int b)
{
if(b==)
return a;
return gcd(b,a%b);//递归调用
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;//利用公式
}
4.其他方法
1.辗转相除法：
又名欧几里德算法（Euclidean algorithm），它是已知最古老的算法， 其可追溯至公元前300年前。
辗转相除法的核心就是不断的让两个数做除法运算。其原理基于两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。
代码如下：
#include<stdio.h>
int main()
{
int x, y, z, m, n;
printf("请输入两个数：");
scanf("%d%d", &x, &y);
m = x, n = y;
while (y != )
{
z = x%y;
x = y;
y = z;
}
printf("最大公约数是: %d\n", x);
printf("最小公倍数是: %d\n", m*n / x);
system("pause");
return ;
}
2.辗转相减法：
即尼考曼彻斯法，其特色是做一系列减法，从而求得最大公约数。
辗转相减法即通过对两数的不断减法运算。
代码如下：
#include<stdio.h>
int main()
{
int x, y, m, n;
printf("请输入两个数：");
scanf("%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 ;
}
3.穷举法：
穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。----来源百度百科
穷举法又称枚举法，通过对数值范围内的所有数字进行检验，得出其结果。
代码如下：
#include<stdio.h>
int main()
{
int x, y, i, m, n;
printf("请输入两个数：");
scanf("%d%d", &x, &y);
m = x, n = y;
for (i = ; i <= x; i++)
{
if (x%i == && y%i == )
break;
}
for (i = x; i > ; i--)
{
if (x%i == && y%i == )
break;
}
printf("最大公约数是: %d\n", i);
printf("最小公倍数是: %d\n", m*n / i);
system("pause");
return ;
}
END
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-07-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
