| 等 级 | |
| 排 名 | 14 |
| 经 验 | 21408 |
| 参赛次数 | 7 |
| 文章发表 | 39 |
| 年 龄 | 0 |
| 在职情况 | 学生 |
| 学 校 | ZUA |
| 专 业 | 计科 |
自我简介：
悄悄地秃头，然后惊艳所有人？
TA的其他文章
你可能喜欢
C语言考试练习题_一元二次方程 （C语言代码）浏览：1918 |
C语言训练-排序问题<1> （C语言代码）浏览：559 |
不知道哪里错了浏览：1141 |
C语言程序设计教程（第三版）课后习题8.3 （C语言代码）浏览：704 |
WU-链表数据求和操作 （C++代码）浏览：1314 |
解题思路:
很多人都用辗转相除法来递归，但是我们上中学时用的更多的应该是短除法，或者叫倒除法，我们进行进制转换时也会用到这种方法
所以我想利用短除法写出代码来表示，也是给大家提供一种不同的思考方式
那么什么是短除法：
假设我们输入 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 人评分
评论区
#include<stdio.h>
int divisor(int m,int n)
{
int d=0;
while(m%n)
{
d=m%n;
m=n;
n=d;
}
return n;
}
int main()
{
int m,n,d,g;
scanf("%d%d",&m,&n);
d=divisor(m,n);
g=n*(m/d);
printf("最大公约数：%d\n最小公倍数：%d\n",d,g);
return 0;
}
有什么问题希望有大佬可以告诉一下
为什么循环i要从2开始，求解？？？？？？？？？？？？？？？？
#include<stdio.h>
int main()
{
int x = 0, y = 0;
scanf("%d%d", &x, &y);
int ret = x * y;
int num = 0;
while (x % y != 0)
{
num = y;
y = x % y;
x = num;
}
printf("最大公约数：%d\n", y);
printf("最小公倍数：%d", ret/y);
return 0;
}
i = 1; //将i重置为1 （循环末尾会i++），为什么要对i进行重置，不懂
寻光 2022-04-02 13:52:42 |
就是再从2开始，依次往后找公因数
#include<stdio.h>
int main()
{
int m,n,t;
scanf("%d%d",&m,&n);
int x=m,y=n;
while(m%n!=0)
{
t=m%n;
m=n;
n=t;
}
printf("%d\n",n);
printf("%d",(x*y)/n);
return 0;
}
请问，为什么要控制j<k呢，谢谢
jxnbhckmshckabckmsbfkdnfjzghsbfkdudn 2022-01-22 13:15:51 |
因为，可能存在i循环到j和k之间，而这样的循环是没有必要的。
精彩推荐
sizeof的大作用 （C语言代码）浏览：1024 |
筛排处理 （C语言代码）浏览：783 |
C二级辅导-分段函数 （C语言代码）浏览：741 |
C语言程序设计教程（第三版）课后习题3.7 （C语言代码）浏览：359 |
C语言程序设计教程（第三版）课后习题5.6 （C语言代码）浏览：525 |
小九九 （C++代码）简单粗暴，直接输出浏览：664 |
C语言程序设计教程（第三版）课后习题9.6 （C语言代码）浏览：2739 |
C语言程序设计教程（第三版）课后习题11.3 （C语言代码）浏览：2114 |
printf基础练习2 （C语言代码）浏览：598 |
校门外的树 （C语言代码）浏览：581 |