解题思路:
欧几里得算法又称辗转相除法，用来求两个正整数的最大公约数。以上面的1997和615为例，用欧几里得算法求解如下：
1997 = 615 * 3 + 152
615 = 152 * 4 + 7
152 = 7 * 21 + 5
7 = 5 * 1 + 2
5 = 2 * 2 + 1
2 = 2 * 1 + 0
当被加的数为0时，可以得出，1997和615的最大公约数为1。
以上做法的依据是以下定理：
两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
用数学表示为： gcd(a, b) = gcd(b, a mod b)
最小公倍数就在算出最大公因数之后就跟简单了：gcd(a, b) * lcm(a, b) = a * b;
注意事项:
参考代码:
#include<stdio.h>
int gcd(int i, int j);
int LCM(int m, int n);
int main(void)
{
int M, N, lcm = 1;
while (scanf("%d %d", &M, &N) != EOF)
{
printf("%d ", gcd(M, N));
printf("%d", LCM(M, N));
}
return 0;
}
int gcd(int i, int j)
{
int mo;
while (j > 0)
{
mo = i % j;
i = j;
j = mo;
}
return i;
}
int LCM(int m, int n)
{
int lcm;
lcm = m * n / gcd(m, n);
return lcm;
}0.0分
21 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
#include<stdio.h> #pragma warning(disable:4996); int ys(int a,int b); int bs(int a,int b); int main() { int a,b; scanf("%d %d", &a, &b); printf("%d %d", ys(a,b), bs(a,b)); return 0; } int ys(int a,int b) { int r=1; while (r!=0)//辗转相除法求最大公约数 { r = a%b; a = b; b = r; } return a; } int bs(int a, int b) { int c=a*b/ys(a,b);//公式最大公约数*最小公倍数=两数之积 return c; }#include<stdio.h> int zdgys(int a,int b) { int c=0; while((a%b)!=0) { int t=0;//保存a的值 t=a; a=b; b=t%b; } return b; } int zxgbs(int a,int b) { int c,d; c=zdgys(a,b); d=(a/c)*(b/c)*c; return d; } int main() { int m,n,i,j; scanf("%d %d",&m,&n); i=zdgys(m,n); j=zxgbs(m,n); printf("%d %d",i,j); return 0; }#include<stdio.h> int main() { int x,y,temp; int i; int a,b; //a为最大公约数，b为最小公倍数 scanf("%d%d",&x,&y); if(x<y) { temp=x; x=y; y=temp; } for(i=y;i>1;i--) { if(x%i==0&&y%i==0) { x/=i; y/=i; a=i; } } b=x*y*a; printf("%d %d\n",a,b); return 0; }我没想到交换算法 #include<stdio.h> int fun(int i, int b); int fun1(int i, int b); int fun(int i, int b) { int num = 0; while (1) { b %= i; if (b == 0) { num = i; break; } i %= b; if (i == 0) { num = b; break; } } return num; } int fun1(int i, int b) { int gcl = (i * b) / (fun(i, b)); return gcl; } int main(void) { int a, b; scanf("%d %d", &a, &b); printf("%d %d", fun(a, b), fun1(a, b)); return 0; }