求最大公约(因)数

求最大公约数

1. 枚举法

• 如果两个数是负数，则需要将其转化为正数。
• 找到两个数中最小的那个，min
• 从(min ~ 1)递减的枚举方式比从(1 ~ ming)递增的方式，效率更高。
• 循环判断min是否为两个数的约数。如果是，min就是最大公约数，break；如果不是，–min，continue。
• 其中将min做为while()的条件，是因为如果min == 0，不进入循环。否则，如果输入的两个数中，不会出现0的话，完全可以使用while(1)，因为至少会在min == 1时，break出循环。

//greatest common divisor
int gcd(int x, int y)
{
	if (x < 0)
		x = -x;
	if (y < 0)
		y = -y;

	int min = x;
	if (y < x)
		min = y;
		
	while (min)
	{
		if (x % min == 0 && y % min == 0)
		{
			break;
		}
		--min;
	}

	return min;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.辗转相除

• 如果两个数中有一个是0的话，返回0
• 如果两个数是负数，则需要将其转化为正数。
• 找到两个数中最下的min，和最大的max
• 得到min除以max的余数rem，在让max = min，min = rem。如果除数min为0了，那么max就是其最大公约数。即：gcd(max ,min)== gcd(min, max%min)

int gcd(int x, int y)
{
	if (x == 0 || y == 0)
		return 0;

	if (x < 0)
		x = -x;
	if (y < 0)
		y = -y;

	int max = x, min = y;
	if (x < y)
	{
		max = y;
		min = x;
	}

	while (min != 0)
	{
		int rem = max % min;
		max = min;
		min = rem;
	}
	return max;
}
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

3.更相减损法

• 如果两个数中有一个是0的话，返回0
• 如果两个数是负数，则需要将其转化为正数。
• 找到两个数中最下的min，和最大的max
• 得到max减min的差dif，在让max = min，min = dif。如果减数min为0了，那么max就是其最大公约数。即：gcd(max ,min)== gcd(min, max-min)

int gcd(int x, int y)
{
	if (x == 0 || y == 0)
		return 0;

	if (x < 0)
		x = -x;
	if (y < 0)
		y = -y;

	int max = x, min = y;
	if (x < y)
	{
		max = y;
		min = x;
	}

	while (min != 0)
	{
		int dif = max - min;
		max = min;
		min = dif;
	}

	return max;
}
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

4.其他

我不确定，对于计算两个数的最大公倍数时，需补需要考虑到0和负数的情况。可以看情况而定，如果确认不会又0和负数，则可以省略前的某些处理。