最大公约数和最小公倍数

发表于

小知识，大挑战！本文正在参与「程序员必备小知识」创作活动

本文已参与 「掘力星计划」 ，赢取创作大礼包，挑战创作激励金。

/***********************************************************************

目的：求输入两个数的最大公约数

分析：确定较大值或较小值，并把较小值拷贝。
最大公约数不会超过两个数的较小值，所以从较小值开始往下找，直到能同时被两个数整除

24 18

24 17

…

25 6

平台：Visual studio 2017 && windows
*************************************************************************/

📝 实现代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
c复制代码#include<stdio.h>
#pragma warning(disable:4996)
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d%d", &m, &n);
	//存储最大公约数
	int gcd = 0;
	//确定最大值为m
	if (m < n)
	{
		int temp = m;
		m = n;
		n = temp;
	}
	//假设最大公约数是n
	gcd = n;
	while (1)
	{
		if (m % gcd == 0 && n % gcd == 0)
		{
			printf("%d\n", gcd);
			break;
		}
		gcd--;
	}
}

/***********************************************************************

目的：优化代码1：

分析：可以不用确定较大值或较小值，但是必须得拷贝一份n或m

18 24

18 23

…

18 6

平台：Visual studio 2017 && windows
*************************************************************************/

📝 优化代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c复制代码#include<stdio.h>
#pragma warning(disable:4996)
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d%d", &m, &n);
	int gcd = 0;
	//假设最大公约数是m
	gcd = m;
	while (1)
	{
		if (m % gcd == 0 && n % gcd == 0)
		{
			printf("%d\n", gcd);
			break;
		}
		gcd--;
	}
}

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++

/***********************************************************************

目的：欧几里德算法 求最大公约数

算法简介：欧几里得算法又称辗转相除法，古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。扩展欧几里得算法可用于RSA加密等领域。

在这里插入图片描述

算法原理：通俗来讲就是以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数

24   18

24 % 18 = 1 … 6

18 % 6 = 3 … 0

平台：Visual studio 2017 && windows
*************************************************************************/

📝 实现代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c复制代码#include<stdio.h>
#pragma warning(disable:4996)
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d%d", &m, &n);
	while(m % n)
	{
		//交换被除数和除数
		int temp = m % n;
		m = n;
		n = temp;
	}
	printf("%d\n", n);
	return 0;
}

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++

/***********************************************************************

目的：更相减损术 求最大公约数

算法简介：《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

image.png

算法原理：

▶ 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

▶ 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

▶ 则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。

在这里插入图片描述

平台：Visual studio 2017 && windows

*************************************************************************/

📝 实现代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
c复制代码#include<stdio.h>
#pragma warning(disable:4996)
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d%d", &m, &n);
	int flag = 0;//为了区分这两个数有没有约简2
	int count = 0;//记录约简了几次2
	int temp = 0;
	while(1)
	{
		//两个数相同
		if(m == n)
		{
			flag = -1;
			break;
		}
		//全为偶
		if(m % 2 == 0 && n % 2 == 0)
		{
			flag = 1;
			count++;
			m /= 2;
			n /= 2;	
		}
		//不全为偶
		else
		{
			//大减小
			if(m > n)
			{
				temp = m - n;
			}
			else
			{
				temp = n - m;
			}
			//比较减数和差
			if(n > temp)
			{
				m = n;
				n = temp;
			}
			else if(n < temp)
			{
				m = temp;
			}
			else
			{
				//减数和差相等
				break;	
			}
		}
	}
	//约简2
	if(1 == flag)
	{
		printf("%d\n", 2 * count * n);
	}
	//两数相等
	else if(-1 == flag)
	{
		printf("%d\n", m);
	}
	else
	{
		printf("%d\n", n);
	}
	return 0;
}

/***********************************************************************

目的：优化 更相减损术 求最大公约数

算法原理：可将上面的步骤理解为：

▶ 若m > n，则m = m - n

▶ 若m < n，则 n = n - m

▶ 若m = n，则最大公约数为m

平台：Visual studio 2017 && windows

*************************************************************************/

📝 优化代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c复制代码#include<stdio.h>
#pragma warning(disable:4996)
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d%d", &m, &n);
	while (m != n)
	{
		if (m > n)
			m -= n;
		else
			n -= m;
	}
	printf("%d\n", m);
	return 0;
}

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++

比较：更相减损术和辗转相除法的主要区别在于前者所使用的运算是“减”，后者是“除”。从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，从而使得算法的时间复杂度退化为O(N)，其中N是原先的两个数中较大的一个。相比之下，辗转相除法的时间复杂度稳定于O(logN)。

这场来自中西方的磨擦就此打住

image.png

当然还有其它的一些算法

穷举法 ：一听就很暴力

Stein算法 ：针对欧几里德算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法

image.png

/***********************************************************************

目的：求输入两个数的最小公倍数

算法原理：

▶ 利用求出最大公约数，用两个数的乘积除以最大公约数即可。

▶ 最小公倍数不会小于两个数的较大值，所以从较大值开始往上找

平台：Visual studio 2017 && windows

*************************************************************************/

📝 实现代码3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c复制代码#include<stdio.h>
#pragma warning(disable:4996)
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d%d", &m, &n);
	//拷贝一份m和n
	int tmp_m = m;
	int tmp_n = n;
	while (m != n)
	{
		if (m > n)
			m -= n;
		else
			n -= m;
	}
	printf("%d\n", tmp_m * tmp_n / m);
	return 0;
}

📝 实现代码4：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
c复制代码#include<stdio.h>
#pragma warning(disable:4996)
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d%d", &m, &n);
	int temp = m;
	while(1)
	{
		if(temp % m == 0 && temp % n == 0)
		{
			printf("%d\n", temp);
			break;
		}
		temp++;
	}
	return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%