Wells

用户名：3180624024

访问量：9982

签　名：

等　　级
排　　名	2595
经　　验	2142
参赛次数	0
文章发表	7
年　　龄	0
在职情况	学生
学　　校	渣渣大学
专　　业	大数据

　　自我简介：

TA的其他文章

数组插入处理（看不懂你打我！！
浏览：4527

自定义函数处理最大公约数与最小公倍数
浏览：143

自定义函数之数字分离
浏览：124

你可能喜欢

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

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

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

点我有惊喜！你懂得！

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

优质题解

欧几里得算法求最大公约数与最小公倍数（思路很简单）

　　作者: Wells　　　　发表时间：2022-04-10 20:52:46 浏览：5708　|　评论：11　

原题链接：[编程入门]自定义函数处理最大公约数与最小公倍数

解题思路:

欧几里得算法又称辗转相除法，用来求两个正整数的最大公约数。以上面的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分

27 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

荆棘鸟的呼唤

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

2023-11-01 21:22:06

3g芯片

#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

2023-07-30 21:07:41

万子龙

作者大大强的呀

2023-04-09 16:46:33

江雪沉月

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

2022-11-19 20:20:44

wdgwthw

你的代码在洛谷里只能得40分欸

2022-06-27 13:51:34

wdgwthw

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

2022-06-27 13:49:40

奋斗的嘉

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

2022-06-27 07:19:27

uq_20099990464

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

2022-06-26 12:59:46