CodeRookie

用户名：Shmily124

访问量：121057

签　名：

清风前烹茶对弈，明月下把酒言欢

等　　级
排　　名	14
经　　验	21404
参赛次数	7
文章发表	39
年　　龄	0
在职情况	学生
学　　校	ZUA
专　　业	计科

　　自我简介：

悄悄地秃头，然后惊艳所有人？

TA的其他文章

蓝桥杯2022年第十三届省赛真题-李白打酒加强版（记忆化搜索+剪枝）C++
浏览：1417

1105: 数列数组模拟与位运算 C/C++
浏览：345

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【偶数求和】（C语言代码）

【排队买票】（C语言代码）

矩形面积交（Java代码）

【出圈】（C语言代码）

优质题解

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

　　作者: CodeRookie　　　　发表时间：2021-01-16 22:05:02 浏览：25682　|　评论：41　

原题链接：[编程入门]最大公约数与最小公倍数

解题思路:

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

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

那么什么是短除法：

假设我们输入 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

图片：

参考代码:

#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;
}

0.0分

259 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

san3ge3san

为啥有个负数就算不了了

2023-05-20 14:25:43

Clospic

循环如果从1开始程序将无法运行，请问这是为什么，求解大佬解答。

2023-03-24 20:42:43

柯拉松

#include <stdio.h>
int main()
{
	int m, n;
	int b;
	printf("请输入m，n的值\n");
	scanf("%d%d", &m, &n);
	int a = m * n;
	if (m > 0 && n > 0) {
		if (m > n) {
			b = n;
		}
		else {
			b = m;
		}
	}
	for (; b > 0; b--) {
		if (m % b == 0 && n % b == 0) {
			break;
		}
	}
	a /= b;
	printf("m,n的最大公约数是%d，最小公倍数是%d", b, a);
        return 0；
}
哪儿错了呀qaq

2023-01-01 14:23:16

柚苏果果

#include<stdio.h>
int main()
{
    int a,b,c=0;
    scanf("%d%d",&a,&b);
    int d=a*b;
    //辗转相除法，a%b=0--b为最大公约数，a为最小公倍数；c=a%b!=0;a=b;b%c=0;c为最大公约数，
    while(1)
    {
        if(a%b==0)
        {
            printf("%d %d",b,d/b);
            break;
        }
        else
        {
            c=a%b;
            a=b;
            b=c;
        }
    }
    return 0;
}
大佬们求指点，这段代码还可以继续优化吗

2022-11-22 20:05:17

uq_50581147706

#include<stdio.h>
int main()
{
	int n,m;
	scanf_s("%d%d", &n, &m);
	for (int i = (m < n) ? m : n; i >0 ; i--) {
		if (!(m % i) && !(n % i)) {
			printf("%d %d", i, m*n/i);
			break;
 		}			
	}
	return 0;
}

2022-10-23 15:11:19

yinhl

为什么循环语句中除和乘都要在i前加一个等号

2022-10-03 15:00:30

干不完

短除法那个代码好像互质情况下不可行啊

2022-10-02 11:48:10

小菜鸟

int main()
{
    int m,n,temp;
    scanf("%d %d",&m,&n);
    for(int i = 0;i<=m;i++)
    {
        if(m % i == 0 && n % i == 0) {
            temp = i;
        }
    }
    printf("%d %d",temp,m * n /temp);
}
这个为什么是错的？

2022-08-07 18:15:42