最大公约数(公因子)多种java实现方法 | 您所在的位置:网站首页 › java怎么实现求多个数和 › 最大公约数(公因子)多种java实现方法 |
最大公因数,也称最大公约数、最大公因子,几个整数,公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。例如:12、16的公约数有1、2、4,其中最大的一个是4,4是12与16的最大公约数. 方法一: 辗转相除法: 如求(9, 15)的 最大公因子 9 / 15 = 0….9 15 / 9 = 1….6 9 / 6 = 1……3 6 / 3 = 2……0 像这样辗转相除, 直到出现余数为零停止, 那么最后的除数就是最大公因子, 即最大公因子等于 3 //辗转相除法 public static int method_one(int a, int b){ return a%b==0 ? b : method_one(b, a%b); }方法二: 更相减损术:如求(9, 15)的 最大公因子 15 - 9 = 6 9 - 6 = 3 6 - 3 = 3 像这样一直用最大的数减去最小的数,直到被减数和差相等,那么减数就是最大公因子, 即最大公因子等于 3 //更相减损法 public static int method_two(int a, int b){ int minValue = a < b ? a : b; //a, b两个数中的最小值 int maxValue = a > b ? a : b; //a, b两个数中的最大值 return minValue == maxValue-minValue ? minValue method_four(minValue, maxValue-minValue); }方法三: 短除法:短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来 ,所得的积就是这几个数的最大公约数。 如求(12, 24)的最大公因子 12 24 | 2 6 12 | 2 3 6 | 3 1 2 最后 1 和 2 都是质数, 最大公因子就等于 2*2*3 = 12 //短除法 static int max = 1; public static int method_three(int a, int b){ int minValue = a < b ? a : b; //a, b两个数中的最小值 for (int i=2; i=2; i--){ if (a % i == 0 && b % i == 0){ return i; } } return 1; }主函数测试结果: |
CopyRight 2018-2019 实验室设备网 版权所有 |