鲁迅说过:“求解最大公约数和最小公倍数有很多方法”,公约数,就是几个数共有的约数,最大公约数,就是公约数中最大的那个数,公倍数,就是几个数共有的倍数,最小公倍数,就是公倍数中最小的那个数。虽然看起来是句废话,其实它就是废话……下面我们看一下求解最大公约数和最小公倍数的几种方法。

求任意两个正整数的最大公约数

最大公约数(Greatest Common Divisor,GCD),先说约数,a能被b整除,b就是a的约数,几个数共有的约数就是这几个数的公约数,公约数中最大的那个数就是最大公约数。举个例子,4和20的公约数有1,2,4,最大公约数是4。可见两个数的最大公约数必不大于两数中最小的那个。

思路一:如果求出最大公约数,穷举法从小到大(从1到两数中较小的一个)遍历,然后输出最大的那个,这样做比较麻烦,不妨我们从大到小(从两数中较小的一个到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
int main()
{
int a = 0;
int b = 0;
int tmp = 0;
int i = 0;
scanf("%d %d", &a, &b);
//a中存储较大的那个数,b存储小数,当a<b时交换两数
if (a < b) {
tmp = a;
a = b;
b = tmp;
}
//从b到1遍历,找最大公约数
for (i = b; i > 1; i--) {
//同时整除两个数的那个数即为所求,找到后break结束遍历
if (a % i == 0 && b % i == 0) {
break;
}
}
printf("%d", i);
return 0;

}

思路二:我们可以用辗转相除法求最大公约数,例如15和20两个数,15%20=15,20%15=5,15%5=0,两数相除,将除数当作下个算式的被除数,余数当作除数,如此往复,当余数为0时,最后一个算式的除数5就是15和20的最大公约数。我可能说的有些复杂了,看代码就懂了,还有这一思路的妙处是不用判断两数的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
int a = 0;
int b = 0;
int c = b;
scanf("%d %d", &a, &b);
//辗转相除,余数为0跳出循环
while (a % b != 0) {
c = a % b;
a = b;
b = c;
}
printf("%d", b);

}

求任意两个正整数的最小公倍数

最小公倍数(Least Common Multiple,LCM),若a能被b整除,a就是b的倍数,对于两个整数来说,两数共有倍数中最小的一个便是最小公倍数。

思路一:我们可以借助最大公约数求最小公倍数。两数乘积除以最大公约数便是最小公倍数。若a和b的最大公约数是c,那么最小公倍数便是a*b/c,最大公约数的求法如上,这一思路这里不再列出代码。

思路二:两个数的最小公倍数就是能被两数整除的那个最小的数(废话文学),如果较大的数能被较小的数整除,那么较大的数就是两数的最小公倍数,否则要从较大的数开始,一次向上遍历,知道找出能同时被两数整除的那个数。举个例子,5和25,25能被5整除,25就是5和25的最小公倍数;5和7,较大的数7不能被5整除,7一直加1,变成8,9,10……,35,知道35,35能被5和7整除,35便是5和7的最小公倍数。废话有点多了,上代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
int a = 0;
int b = 0;
int tmp = 0;
int i = 0;
scanf("%d %d", &a, &b);
//a存放两数中较大的那个,b存放小数
if (a < b) {
tmp = a;
a = b;
b = tmp;
}
//从最大数开始向上计数
for (i = a; i > 0; i++) {
//找出最小公倍数,退出循环
if (i % a == 0 && i % b == 0) {
break;
}
}
printf("%d", i);

}

思路三:众所周知,5和7的最小公倍数是35,35能被5和7同时整除(又是一句废话),看下面这个算式:5*i%7=05*i的结果既能被5整除,也能被7整除,所以5*i便是5和7的最小公倍数。

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
int a = 0;
int b = 0;
int i = 1;
scanf("%d %d", &a, &b);
while (a * i % b) {
i++;
}
printf("%d", a * i);
return 0;
}