CodeRookie

用户名：Shmily124

访问量：133464

签　名：

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

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

　　自我简介：

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

TA的其他文章

2571: 蓝桥杯2020年第十一届省赛真题-回文日期（C++）
浏览：1439

2606: 蓝桥杯2021年第十二届省赛真题-左孩子右兄弟（C++）
浏览：1952

2612: 蓝桥杯2021年第十二届省赛真题-最少砝码
浏览：499

你可能喜欢

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

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

格式错误一万年，，有没有过了的来看看（终于过了）

C二级辅导-同因查找（C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

优质题解

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

　　作者: CodeRookie　　　　发表时间：2021-01-16 22:05:02 浏览：27848　|　评论：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分

271 人评分

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

　　评论区

白色枫叶

#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

2021-09-17 11:11:17

Drgeek

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

2021-07-29 19:30:23

winnie

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

2021-07-08 15:39:10

那咕

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

2021-05-26 16:14:38

cando

#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;
}
我的运行结果没错呀，为什么一直显示答案错误

2021-04-09 12:01:57

渴望学到知识的菜鸟

强无敌啊，就是为啥最小公倍数是那几个相乘呢

2021-03-30 17:24:03

你胜过世间万物

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



这个为什么不对啊

2021-03-27 20:34:54

linaki