当前位置:码农谷 > 算法与程序 > 最大公约数和最小公倍数问题的完整程序源码

最大公约数和最小公倍数问题的完整程序源码

所属学科:C语言 难度: 关注度:453

问题

输入两个正整数m和n,求其最大公约数和最小公倍数。

辗转相除法

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的:若 r 是 a ÷ b 的余数, 则gcd(a,b) = gcd(b,r)a 和其倍数之最大公因子为 a。另一种写法是:a ÷ b,令r为所得余数(0≤r<b)若 r = 0,算法结束;b 即为答案。互换:置 a←b,b←r,并返回第一步。

程序源码

完整的程序源代码如下:

#include "stdio.h"
 
int gcd(int a,int b)//最大公约数
{
    if (a<b) return gcd(b,a);
    else if (b==0) return a;
    else return gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
void main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("最大公约数:%d\n",gcd(a,b));
    printf("最小公倍数:%d\n",lcm(a,b));
}

另外一种实现方法

输入两个正整数m和n, 求其最大公约数和最小公倍数.<1>用辗转相除法求最大公约数 算法描述: m对n求余为a, 若a不等于0 则 m <- n, n <- a, 继续求余 否则 n 为最大公约数<2>最小公倍数 = 两个数的积 / 最大公约数。

程序源码

#include "stdio.h"
 

关注微信,获得更多免费资源
关于我们   |   免责声明   |   联系我们   |   网站地图   |   HR交流群   |   学生交流群   |   教师交流群

码农谷   版权所有 © 2015-2017   湘ICP备16018319号-1