最大公约数

首先做这个题需要先复习几组概念：

如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。
几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。
举例：

12，16
12的约数有：1，2， 3， 4， 6， 12
16的约数有：1， 2， 4， 8， 16
故而最大的公约数为4。

求最大公约数有多种方法，常见的有辗转相除法。

 1 private static int getMaxCommonDivisor(int a, int b) {

 2     // 使a小,b大

 3     if(a > b){

 4         // 两个数交换

 5         a = a + b;

 6         b = a - b;

 7         a = a - b;

 8     }

 9     int temp = a;

10     while(temp > 0){

11         if(a % temp == 0 && b % temp == 0){

12             break;

13         }

14         temp--;

15     }

16     return temp;

17 }

观察性质或者案例，我们可以知道最大公约数一定满足（对于数A和数B来说，最大公约数C），A%C=0且B%C=0。且最大。

巴特西

java入门与进阶P-4.7

最大公约数

最新文章

热门文章