解题思路:
欧几里得算法又称辗转相除法，用来求两个正整数的最大公约数。以上面的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> int main() { int m,n,a,b,c; scanf("%d%d",&m,&n); c=m*n; b=0; while(n!=0) { b=n; n=m%n; m=b; } printf("%d\n",m); printf("%d",c/m); return 0; }#include <stdio.h> #define NUMBER 2 int number_factors(int m , int n); int number_multiple(int m, int n); void main(void) { int i,j; scanf("%d %d",&i,&j); printf("%d\n",number_factors(i,j)); printf("%d\n",number_multiple(i,j)); return 0; } int number_factors(int m, int n) { int i, j ,k; int temp; if(m > n) temp = m; else temp = n; for (i = 1; i < temp; i++) { if(m%i == 0 && n%i == 0) j=i; } return j; } int number_multiple(int m, int n) { int i, j ,k; int temp; if(m > n) temp = m; else t#include<stdio.h> int YueshuMax(int a,int b); int BeishuMin(int a,int b); int main() { int M,N; scanf("%d %d",&M,&N); printf("%d %d\n",YueshuMax(M,N),BeishuMin(M,N)); return 0; } int YueshuMax(int a,int b) { if(a%b==0) return b; else return YueshuMax(b,a%b); } int BeishuMin(int a,int b) { int X; X=a*b/YueshuMax(a,b); return X; }@奋斗的嘉 #include<stdio.h> #include<math.h> int main() { int m(int,int); int n(int,int); int a,b; scanf("%d%d",&a,&b); printf("%d %d",m(a,b),n(a,b));这段代码·是什么意思？#include <iostream> #include <algorithm> using namespace std; int main() { int a, b; cin >> a >> b; int n, m; n = a,m = b; if(a==1||b==1) // 两个正整数中，只有其中一个数值为1，两个正整数为互质数 return true; while(1){ // 求出两个正整数的最大公约数 int t = a%b; if(t == 0) break; else{ a = b; b = t; } } if(b>1) cout << b << " " << n*m/b;// 如果最大公约数大于1，表示两个正整数不互质 else cout << 1 << " " << n*m; // 如果最大公约数等于1,表示两个正整数互质 return 0; }#include<stdio.h> #include<math.h> int main() { int m(int,int); int n(int,int); int a,b; scanf("%d%d",&a,&b); printf("%d %d",m(a,b),n(a,b)); } int m(int a,int b){ int i,m; for(i=1;i<=a;i++){ if(a%i==0&&b%i==0){ m=i; } } return m; } int n(int a ,int b) { int i; for(i=a;;i++){ if(i%a==0&&i%b==0){ break; } } return i; }