题目

描述

• 求出两个数的最大公约数，如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

方法一

思路

• 找出两个数a,b的最大公约数，暴力遍历，首先找出a与b中的最小值，然后从最小值开始往下遍历，找到的第一个公约数即为最大公约数。1一定是a与b的公约数。
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    public int gcd (int a, int b) {
        // 找出最小值
        int min = Math.min(a,b);
        while(min > 0){
            // 判断是否为公约数
            if (a % min == 0 && b % min == 0){
                return min;
            }
            --min;
        }
        return 1;
    }
  }

• 时间复杂度：，a与b的最大公约数为1，此时需要遍历min{a,b}次；
• 空间复杂度：，常数级空间复杂度。

方法二

思路

• 辗转相除法，欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式:
• 用大数对小数求余，若余数为0，则除数为最大公约数。若余数不为0，将此余数作为除数，小数作为被除数，重新求余，直到余数为0为止。此时的最大公约数为余数。
• 参考下图示例：
  
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    public int gcd (int a, int b) {
        // 将a置为较大值
        if(a < b){
            swap(a,b);
        }
        // 辗转相除法
        while(b != 0){
            int c = a % b;
            a = b;
            b = c;
        }
        return a;
    }
    // 通过位运算实现值交换
     private void swap(int a, int b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
  }

• 时间复杂度：,逆着看该算法,最后的余数是0,倒数第二次余数是d,倒数第三次是kd,k>1…，由于组成了一个数列,{0,d,kd,nkd+d,…}，数列的n项加上n+1项,比n+2项要小,所以比斐波纳契数列增长的要快。斐波纳契数列增长速度是指数,那么待分析的数列也是指数增长。设欧几里得算法需要k次,那么,则；
• 空间复杂度：，常数级空间复杂度。