Java实现求最大公约数

欧几里德定理简述如下：
有非负整数：p, q, r, n, k，若 q 与 p 的最大公约数为 k，设：
p = n1 * k , q = n2 * k, p = n * q + r 则有： q 与 r 的最大公约数也是 k。简单地说 若 p = n * q + r ，那么 p 与 q 的最大公约数就是 q 与 r 的最大公约数。
先从数学的角度证明一下该定理：
因为 p = n1 * k ， q = n2 * k ， p = n * q + r 所以 p - n * q = r， 即：
r = n1 * k - n * n2 * k , 又 k 是 q = n1 * k 与 q = n2 * k 的最大公约数，所以 ： n1 与 n2 没有除 1 以外的其他公约数，所以 k 是 r = n1 * k - n * n2 * k 与 q = n2 * k 的最大公约数，定理得证。
附上 Java 实现 的 欧几里德算法求最大公约数( Greatest common divisor )代码：

public static int gcd(int p, int q) {
   if(q==0){
     return q;
   }
   int r = p % q ;
   return gcd(q, r);
}

Java实现蛮力法求最大公约数( Greatest common divisor )代码：

在这里插入代码片
```public static int gcd1(int p, int q){
      // num 用来存放最大公约数，默认为 1
      int num = 1;
      if( p <= q ) {
            int k ;
            k = q ;
            q = p;
            p = k;
      }
   for(int i = 1 ; i < Math.sqrt( q) ; i++){
        // 判断 i 是 否是 q 的约数，如果是，再判断 i 是否是 p的约数
         if( q %i== 0 ){
                if( p % i == 0 ){
                      num = i;
                }
                
                // 若  i 是 q 的约数， 那么 q / i 也是 q 的约数
                if( p % ( q / i ) == 0) {
                   num = q / i ;
                  return num ;
                 }         
        }
}
return num ;
}

上面两种方法都可以求最大公约数，欧几里德定理使用递归实现的方式非常简洁

最后

以上就是有魅力泥猴桃为你收集整理的Java实现求最大公约数的全部内容，希望文章能够帮你解决Java实现求最大公约数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。