CodeRookie


私信TA

用户名：Shmily124

访问量：133494

签　名：

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

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

　　自我简介：

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

TA的其他文章

蓝桥杯2022年第十三届省赛真题-李白打酒加强版（记忆化搜索+剪枝）C++
浏览：1502
1105: 数列 数组模拟与位运算 C/C++
浏览：415

你可能喜欢

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

浏览：810

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

浏览：1059

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

浏览：674

C语言训练-大、小写问题 （C语言代码）

浏览：2421

C二级辅导-进制转换 （C语言代码）

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

解题思路:


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

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

那么什么是短除法：

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


　

0.0分

271 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

int gys(int a, int b) {
	if (a % b == 0) return b;
	else return gys(b, a % b);
}
int main()
{
    int a,b,max=0,gbs=0,gyss;
	scanf("%d%d", &a,&b);
	max = a;
	if (b > a) max = b, b = a;
	gyss = gys(max, b);
	gbs = max * b / gyss;
printf("%d %d", gyss,gbs);
    return 0;
}
2024-03-24 23:58:34 
#include<stdio.h>
#include<math.h>
int main()
{
    int a,b,c;
    scanf("%d %d",&a,&b);
    for(int i=a;i>0;i--){//最大公约数在1到其中一个值之间
        if(a%i==0&&b%i==0)
        printf("%d ",i);
    }
    c=a*b;
    for(int j=a;j<=c;j++){//最小公倍数结果在其中一个元素到他们乘积之间
        if(j%a==0&&j%b==0){
            printf("%d",j);
        }
    }
    
}
这么写为啥只有50分
2024-03-24 12:08:17 
#include<stdio.h>

int main()
{
	int a,b,c,d,j;
	long long i;
	scanf("%d%d",&a,&b);
	c=a>b?a:b;
	d=a<b?a:b;
	
	for(j=c;j>=1;j--)
	{
		if(a%j==0&&b%j==0)
		{
			printf("%d\n",j);break;
		}
	}
	for(i=d;i<1000000;i++)
	{
		if(i%a==0&&i%b==0)
		{
			printf("%d\n",i);break;
		}	
	}
	return 0;
}
2024-03-05 21:27:27 
#include<stdio.h>
void main()
{
	int m,n;
	//printf("请输入两个正整数\n");
	scanf("%d%d",&m,&n);
	
	int yue,bei;
	int i=1;
	int ok=0;
	for(i=1;i<=m/2&&i<=n/2;i++)
	{
		if(m%i==0&&n%i==0)
			yue=i;
	}
	bei=(m/yue)*(n/yue)*yue;
	//printf("最大公约数为\n");
	printf("%d\n",yue);
	//printf("最小公倍数为\n");
	printf("%d\n",bei);
}
2023-12-29 20:08:57 
#include<stdio.h>
int main()
{
	int a,b,i;
	scanf("%d%d",&a,&b);
	for(i=1;i< a>b?a:b;i++){
	    if(a%i==0&&b%i==0){
	        printf("%d",i);
	        break;
	    }
	}
	
	printf(" ");
	
		for(i=a>b?a:b; ;i++){
	    if(i%a==0&&i%b==0){
	        printf("%d",i);
	        break;
	    }
	}
	return 0;
}

为啥只有50分这样写，也没错啊
2023-12-08 16:09:23 
您好，短除法求公约公倍那边好像有点问题。比如说，我输入2和3两个数字。很明显它们的最大公约数是1，最小公倍数是6。而根据您for循环的里的判断结果，最大公约数是2，很明显不符合。所以需要修改一下。
#include<stdio.h>
int main()
{
	int a,b,t=1;
	scanf("%d %d",&a,&b);
	for(int i=1;i<=a&&i<=b;i++)
	{
	    if(a%i==0&&b%i==0)
	    {
	        a/=i;
	        b/=i;
	        t*=i;
	    }
	}
	printf("%d\n%d",t,a*b*t);
	return 0;
}
这样就可以了，希望您能采纳并及时修改。
2023-11-30 20:59:17 
#include<stdio.h>
int main()
{
    int m,n,X,Y;
    printf("请输入两个正整数m,n：");
    scanf("%d%d",&m,&n);
    X=m*n;
    if(m>0&&n>0)
  {
    while(m!=n)
    {
        if(m>n)
        {
            m=m-n;
        }
        else if(m<n)
        {
            n=n-m;
        }
    }
    else
    printf("error！\n");
  }
    printf("最大公约数是%d\n",m);
    Y=X/m;
    printf("最小公倍数是%d\n",Y);
    return 0;
}
哪里错了
2023-11-01 17:55:39 
#include <stdio.h>
int main()
{
    int x,y,m,n,min,max;
    scanf("%d%d",&x,&y);
    m=x;
    n=y;
    if(x>y)
    {
        m=y;
        n=x;
    }//确保m小
    for(int i=m;i<=m;i--)
    {
        if(m%i==0&&n%i==0)
       { 
           max=i;
           break;//退出for循环
       }
    }
    for(int j=1;j<=m;j++)
    {
        if(j*m%n==0)
        {
            min=j*m;
            break;//退出for循环
        }
    }
    printf("%d %d",max,min);
    return 0;
}
哪里错了，一直显示答案错误
2023-08-18 21:04:50

精彩推荐

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

浏览：512

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

浏览：2121

C语言训练-数字母 （C语言代码）

浏览：648

【亲和数】 （C语言代码）

浏览：628

妹子杀手的故事 （C语言代码）

浏览：1153

输入输出格式练习 （C语言代码）

浏览：773

找出最长的字符串来 （C语言代码）

浏览：1840

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

浏览：856

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

浏览：504

简单的a+b （C语言代码）

浏览：497