1. Dotcpp
  2. 题解列表
  3. 1011题题解

[编程入门]最大公约数与最小公倍数-题解（C语言代码）(短除法)

30669 阅读 90 评论
原题链接：[编程入门]最大公约数与最小公倍数

解题思路:


很多人都用辗转相除法来递归，但是我们上中学时用的更多的应该是短除法，或者叫倒除法，我们进行进制转换时也会用到这种方法

所以我想利用短除法写出代码来表示，也是给大家提供一种不同的思考方式

那么什么是短除法：

假设我们输入 m=12，n=18 ，初始化最大公约数 gcd=1

我们发现 2 是12和18的一个公因子

我们令 m /= 2 ，n /= 2 ，gcd *= 2 

现在 m == 6 ,  n == 9 ,  gcd == 2

又发现 3 是 6 和 9 的一个公因子

我们令 m /= 3 ,  n /= 3 ,  gcd *= 3

现在m == 2 ,  n == 3 ,  gcd == 6

我们找不到除 1 以外的 2 和 3 的公因子了

所以现在的 gcd == 6 就是我们要找的最大公因数

而最小公倍数 lcm = gcd * m * n = 6 * 2 * 3 = 36


图片：

20200421113208150.jpg


参考代码:

#include <stdio.h>
int main()
{
    int m, n;
    int j, k;
    int lcm, gcd = 1;
    scanf("%d %d", &m, &n); //输入m和n
    j = m, k = n;           //用j和k表示m和n，不破坏m与n的值
    if (j > k)
    {
        j = n, k = m; //确保j是较小的那个
    }
    for (int i = 2; i <= j; i++) //循环寻找从i到j的因子（注意j是可变的，而i会被重置）
    {
        if (j % i == 0 && k % i == 0) //判断i是否为j和k的公因子
        {
            j /= i;
            k /= i;   //j与k分别除以i
            gcd *= i; //gcd乘以i
            i = 1;    //将i重置为1 （循环末尾会i++）
        }
    }
    lcm = gcd * j * k;         //求出最小公倍数lcm
    printf("%d %d", gcd, lcm); //输出gcd与lcm
    return 0;
}


看了评论区的诸多意见，决定重写这份时隔一年的代码：

//短除法求公约公倍 
#include <stdio.h>

int main() {
	int m, n;
	scanf("%d %d", &m, &n); 
	int gcd = 1;
	for (int i = 2; i <= m && i <= n; i++) {
		while (m % i == 0 && n % i == 0) { 
			m /= i;
			n /= i;
			gcd *= i;
		}
	}
	printf("%d %d\n", gcd, m * n * gcd);
	return 0;
}


短除法可能便于理解，但效率其实并不理想，时间复杂度可以达到O(n)（当输入质数时）

而辗转相除法被推断出时间复杂度为 O(log(n))

所以还是建议使用辗转相除法，代码量少且运算速度快：

//辗转相除法求公约公倍 
#include <stdio.h>

int gcd(int a, int b) {
	return (a % b == 0) ? b : gcd(b, a % b); 
}

int main() {
	int m, n;
	scanf("%d %d", &m, &n); 
	int ans = gcd(m, n);
	printf("%d %d\n", ans, m * n / ans);
	return 0;
}


点赞(4)
　

0.0分

208 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

2844: 大整数的因子 　　 文章 > 编写题解
2844: 大整数的因子 　　 文章 > 编写题解
蓝桥杯算法提高VIP-单词个数统计
蓝桥杯算法提高VIP-单词个数统计
组合输出（从n个数中选择r个数 进行组合）利用深度优先遍历
组合输出（从n个数中选择r个数 进行组合）利用深度优先遍历
分解因数（一个数 因数的组合有多少个 利用递归）
分解因数（一个数 因数的组合有多少个 利用递归）

评论列表 共有 90 条评论

那咕 4年前 回复TA 
#include<stdio.h>
int main()
{
int n,m;
scanf_s("%d%d"&n,&m);
int x[20];int a,b;static y=0;
a=n>m?n:m;
for(size_t i=1;i<=a;i++)
{
if((!(n%i))&&(!(m%i)))
{x[y]=i;y++;}
}
for(size_t i=0;i<=y;i++)
{if(x[0]<x[i])
{x[0]=x[i];}
}
b=x[0]*(n/x[0])*(m/x[0]);
printf("%d %d",x[0],b);
渴望学到知识的菜鸟 4年前 回复TA 
@渴望学到知识的菜鸟 @cando 嗯，对，我之前不知道【笑哭】
cando 4年前 回复TA 
@渴望学到知识的菜鸟 最小公倍数不就是两个数相乘再除以他们的公因数吗
CodeRookie 4年前 回复TA 
@cando 兄弟，你但凡随便试两个正常的数字都能找到问题，比如 2 和 4，你应该在for循环里的 if 语句里加一句 break; 找到答案了就该停下来
cando 4年前 回复TA 
#include<stdio.h>
int main()
{
    int m,n,j,k;
    scanf("%d %d",&m,&n);
    j=n;
    if(j<m)
    j=m;
    for(k=j;k>=1;k--)
    {if(m%k==0&&n%k==0)
    printf("%d %d",k,m*n/k);}
    return 0;
}
我的运行结果没错呀，为什么一直显示答案错误
渴望学到知识的菜鸟 4年前 回复TA 
强无敌啊，就是为啥最小公倍数是那几个相乘呢
你胜过世间万物 4年前 回复TA 
#include <stdio.h>


int main()
{
    int m;
    int n;
    int z;
    int x;
    int c;
    int v;
    scanf("%d %d",&m,&n);
    if(m<n)
        {z=n;
        x=m;}
    else {z=m;
         x=n;}
    while (c!=0)
    {
         c=z%x;
         z=x;
         x=c;
    }
    v=(m*n)/z;
     printf("最大公约数%d 最小公倍数%d",z,v);
}



这个为什么不对啊
linaki 4年前 回复TA 
可以的
tiger 4年前 回复TA 
@tiger 感觉短除法容易理解多了，谢谢大佬指点
tiger 4年前 回复TA 
#include<stdio.h>
int main()
{
	int m,n,gcd=1,a,b,phd,i;
	scanf("%d%d",&m,&n);
	a=m,b=n;
	for(i=2;i<=m&&i<=n;i++)
	{
		if(m%i==0&&n%i==0)
		{
			gcd=gcd*i;
			a=a/i;
			b=b/i;
			
		}
		
	}
	phd=a*b*gcd;
	printf("%d %d\n",gcd,phd);
	return 0;
}