其他算法|Java求两个自然数的最大公约数其他算法|java

【其他算法|Java求两个自然数的最大公约数】
1、递减法，时间复杂度有点高：o(n)

public class Maximum {public static void main(String[] args) {System.out.println("result:"+getCommonNum(13, 11)); // System.out.println("result:"+getCommonNum1(6, 12)); }private static String getCommonNum(Integer a, Integer b) { if(a <= 0 || b <= 0) { return "零或负数无最大公约数"; } if(a.compareTo(b) == 0) { return "最大公约数为："+a; //相同则互为最大公约数 } else { int temp; if(a.compareTo(b) < 0) { temp = b; b = a; a = temp; //互换保证a>b } int c = b; while (c > 1) {//等于1时候最大公约数就是b本身。 if(a%c == 0 && b%c == 0){//第一次能除开就是最大的约数 break; } c--; //c从b开始递减； } return "最大公约数为：" + c; } } }

2、辗转相除法,效率高

private static String getCommonNum1(Integer a, Integer b) { if(b == 0) { return "最大公约数"+a; } return getCommonNum1(b, a%b); }

原理：利用递归方式找到最大公约数
1:a/b = q 余数是r1
如果r1 = 0,则说明a是b的整数倍，最大公约数就应该是b
如果r1!= 0,则说明a不是b的整数倍，b/r1 = p余数是r2
如果r2 =0，则说明最大公约数就应该是r1
如果r2 !=0, 则说明最大公约数不是r1，继续上述操作。r1/r2=w...r3
如果r3.......
例子：（12，10）
12/10=1...2
(10,2)
10/2=5...0
此时进入递归a=2,b=0时遇到代码if(b == 0) { return "最大公约数"+a; }跳出循环最大公约数为2.

3、交替相减法；最大时间复杂度也很高。

private static String getCommonNum2(Integer a, Integer b) { if(b == a) { return "最大公约数"+a; } if(a > b) { return getCommonNum2(a - b, b); }else { return getCommonNum2(b - a, a); }}