几种求最小公约数和最大公倍数的思考(C语言实现)-创新互联

首先我们得先搞清楚大公约数和最小公倍数的定义.

大公约数:两个或多个整数共有约数中大的一个,例如,6和9的大公约数是3.

最小公倍数:两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数,例如,6和21的最小公倍数是42.

一.辗转相除法.

有两个整数a和b

1.a%b = temp; 若temp=0;此时b就是a和b的大公约数

2.若b≠0,则a=b;b=temp;继续a%b的操作

3.例如.21和6,  21%6余3; 6%3余0;此时3就是他们的大公约数 

4.得到大公约数后,用这两个数的乘积除以他们的大公约数就得到了最小公倍数,例如,6和21,大公约数为3, (6*21)/3 = 42; 42就是他们的最小公倍数.话不多说上代码

#define _CRT_SECURE_NO_WARNINGS 1
#include//辗转相除法,乘积除以大公因数得到最小公倍数
int fib(int a, int b)
{
	while (a*b!=0)
	{
		int tmp = a % b;
		a = b;
		b = tmp;
	}
	//printf("%d %d\n", a, b);
	return a;
	
}
int main()
{
	int a = 0;
	int b = 0;
	printf("请输入两个数:>\n");
	scanf("%d %d", &a, &b);
	int sum = a * b;
	int m = fib(a,b);
	
	printf("大公约数 = %d\n", a);

	printf("最小公倍数 = %d\n",sum/m);

	return 0;
}

运行结果

二.更象相减

1. 若a >b,则 a = a - b；

2. 若a< b,则 b = b - a；

3. 若 a = b,则 a(b)即为两数的大公约数

4.若 a ≠ b,则继续执行第一步操作。

5.例如21和6.  21-6=15(15>6); 15-6=9(9>6); 9-6=3(3<6); 6-3=3(3=3)//  3就是这两个数的大公约数,同理,同样的办法可以得到两个数的最小公倍数,上代码

int fib(int a, int b)
{
	while (a != b)
	{
		if (a >b)
		{
			a = a - b;
		}
		else
		{
			b = b - a;
		}
	}
	return a;
}
int main()
{
	int a = 0;
	int b = 0;
	printf("请输入两个数;>\n");
	scanf("%d %d", &a, &b);
	int sum = a * b;

	int m = fib(a, b);

	printf("大公约数 = %d\n", m);
	printf("最小公倍数 = %d\n", sum/m);


	return 0;
}

运行结果

三.硬算(穷举).

有两个整数a和b：

从1开始,让a和b同时除以,直到某个数同时满足被a和b整除,此时这个被整除的数字就是大公约数,同样道理,可以获得最小公约数.上代码

int fib(int a, int b)
{
	
	int n = 0;
	for (int i = 1; i< b; i++)//i小于a和b任意一个都行
	{
		if ((a % i == 0) && (b % i == 0))
		{
			n = i;
		}
	}
	return n;
}
int main()
{
	int a = 0;
	int b = 0;
	printf("请输入两个数;>\n");
	scanf("%d %d", &a, &b);
	int sum = a * b;

	int m = fib(a, b);

	printf("大公约数 = %d\n", m);
	printf("最小公倍数 = %d\n", sum/m);


	return 0;
}

运行结果

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧