解题思路:
很多人都用辗转相除法来递归，但是我们上中学时用的更多的应该是短除法，或者叫倒除法，我们进行进制转换时也会用到这种方法
所以我想利用短除法写出代码来表示，也是给大家提供一种不同的思考方式
那么什么是短除法：
假设我们输入 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分
208 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
//看那些i j k通常好头大，我喜欢有点可读性 #include <stdio.h> int main(int argc, char* argv[]) { int maxFac =1, minMult = 1, a, b, i; scanf("%d%d", &a, &b); for (i = 1; i <=a; i++){ if (a%i == 0 && b%i == 0) { maxFac = i; } minMult = a*b/maxFac; } printf("%d %d\n", maxFac,minMult); return 0; }#include<stdio.h> int main() { int n,m,a,b; scanf("%d%d",&n,&m); a=m/n; b=n*m; printf("%d %d\n",a,b); return 0; } 我的结果没错但是没通过#include <stdio.h> int main () { int a,b; int c;//中间量 scanf("%d%d",&a,&b); int x=a,y=b;//储存初始输入值 while(1){ if(a<b){ c=a;a=b;b=c; } a%=b; float n=a,m=b; if(a/b==n/m) break;//根据两值是否相等，判断是否除尽，是则跳出循环 } printf("%d\n",b); printf("%d\n",x*y/b); return 0; }#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; }