| 等 级 | |
| 排 名 | 14 |
| 经 验 | 21404 |
| 参赛次数 | 7 |
| 文章发表 | 39 |
| 年 龄 | 0 |
| 在职情况 | 学生 |
| 学 校 | ZUA |
| 专 业 | 计科 |
自我简介：
悄悄地秃头，然后惊艳所有人？
TA的其他文章
你可能喜欢
弟弟的作业 （C语言代码）浏览：3680 |
C语言训练-自由落体问题 （C语言代码）浏览：794 |
假币问题 （C++代码）（向上取整的一种处理方式）浏览：1661 |
C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）浏览：494 |
C语言训练-角谷猜想 （C++代码）（3N+1问题）浏览：1750 |
解题思路:
很多人都用辗转相除法来递归，但是我们上中学时用的更多的应该是短除法，或者叫倒除法，我们进行进制转换时也会用到这种方法
所以我想利用短除法写出代码来表示，也是给大家提供一种不同的思考方式
那么什么是短除法：
假设我们输入 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 main()
{
int m,n,x;
int p=1;
int z;
scanf("%d %d",&m,&n);
x=m*n;
if(m>n){
while(p!=0){
p=m%n;
m=n;
n=p;
}
printf("%d ",m);
printf("%d",z=x/m);
}else{
while(p!=0){
p=n%m;
n=m;
m=p;
}
printf("%d ",n);
printf("%d",z=x/n);
}
return 0;
}
辗转相除法永远滴神XDDDDDDDDDD
#include"stdio.h"
int main (){
//求输入的两个数的最大公约数和最小公倍数，先分析，最小公倍数的特点就是这个数一定大于等于这两个数中的最大数，
//最大公约数一定小于等于两个数中的最小数
int a,b,temp,min,max;
scanf("%d %d",&a,&b);
//先求最大公约数
if(a>b)
{min=b;
}
else{min=a;
}
while(a%min||b%min){
//或者 是两者都为假就不执行，那么只要其中有一个为真就执行这个循环，说明其中有一个取余不等于0，那这个数就不是两个的公共约数
min--;
}
printf("%d ",min);
//求最小公倍数
if(a>b)
{max=a;
}
else{max=b;
}
while(max%a||max%b){
max++;
}
printf("%d",max);
return 0 ;
#include"stdio.h"
#include <string.h>
int main(void)
{
int a,b,min,max;
scanf("%d %d",&a,&b);
for(int i = a*b;i>0;i--)
{
if(i%a==0 && i%b==0&&(i/a==1||i/b==1))
{
min = i;
printf("最小公倍数%d\n",i);
}
if(i==1&&min==0)
{
min = a*b;
printf("最小公倍数%d\n",min);
}
}
for(int i = a*b;i>0;i--)
{
if(a%i==0 && b%i==0 && i!=1)
{ max = i;
printf("最大公约数%d\n",i);
break;
}
if(i==1 && max==0)
{
max = 1;
printf("最大公约数%d\n",max);
}
}
return 0;
}
#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);
#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;
}
我的运行结果没错呀，为什么一直显示答案错误
CodeRookie 2021-04-09 12:46:04 |
兄弟，你但凡随便试两个正常的数字都能找到问题，比如 2 和 4，你应该在for循环里的 if 语句里加一句 break; 找到答案了就该停下来
强无敌啊，就是为啥最小公倍数是那几个相乘呢
#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);
}
这个为什么不对啊