最大公約數(shù)和最小公倍數(shù)是我們小學(xué)學(xué)習(xí)的，那時(shí)候我們求最大公約數(shù)，往往是將兩數(shù)的所有約數(shù)全部列出來(lái)，然后找出共有的約數(shù)中其中最大的那個(gè)；而求最小公倍數(shù)也往往是將兩數(shù)的倍數(shù)一一列出，找出相等的倍數(shù)中最小的那個(gè)。

好吧??，原諒我的無(wú)知。。。原來(lái)還可以用短除法求最大公約數(shù)和最小公倍數(shù)，小學(xué)白學(xué)了??，一直窮舉窮舉了六年，我枯了??。

短除法

最小公倍數(shù)：

使用計(jì)算機(jī)編程計(jì)算最小公約數(shù)和最小公倍數(shù)有很多種方法，下面將進(jìn)行總結(jié)。

1. 最大公約數(shù)

求最大公約數(shù)的方法我總結(jié)了4種方法：

1. 窮舉法
2. 輾轉(zhuǎn)相除法
3. 更相減損術(shù)
4. 算法

下面分別講解：

1.1 窮舉法

• 分析：窮舉法是最笨，但是最容易想到的方法??。根據(jù)定義，我們只需找出一個(gè)數(shù)能同時(shí)被兩個(gè)數(shù)整除，且為此類(lèi)數(shù)中最大的一個(gè)即可。取兩個(gè)數(shù)中較小的數(shù)，從這個(gè)數(shù)開(kāi)始遞減，直到能同時(shí)被兩個(gè)數(shù)整除，則此時(shí)，可求得最大公約數(shù)。

• 代碼實(shí)現(xiàn)

  public static int maxNum(int numA, int numB) {
    int i;
    for(i = numA > numB ? numB : numA; i > 0; i--) {
        if((numA % i == 0) && (numB % i == 0)) {
            break;
        }
    }
    return i;
  }
  

1.2 輾轉(zhuǎn)相除法(歐幾里得算法)

輾轉(zhuǎn)相除法，又名歐幾里得算法，其基本原理： 兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù) 。一看這基本原理是不是激動(dòng)了一下??，又可以用遞歸了。下面給出遞歸和非遞歸的兩種實(shí)現(xiàn)。具體介紹詳見(jiàn)維基百科

維基百科錯(cuò)誤

(這怕是假的維基百科，還真像《瑞克和莫蒂》中說(shuō)的一樣，誰(shuí)都可以寫(xiě)。。。確實(shí)誰(shuí)都可以寫(xiě)23333??。輾轉(zhuǎn)相除法和更相減損術(shù)傻傻分不清??，我已提交錯(cuò)誤)。

1.2.1 非遞歸實(shí)現(xiàn)

• 分析：取這兩個(gè)數(shù)，將大數(shù)放在numA中，小數(shù)放在numB中，求numA除以numB的余數(shù)，放在temp中，根據(jù)輾轉(zhuǎn)相除法(歐幾里得算法)，兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。如果余數(shù)temp不為 ，一直循環(huán)將numB值賦給numA，temp值賦給numB，再對(duì)numA和numB求余，直到余數(shù)temp為 ，則此時(shí)numB為最大公約數(shù)。

• 代碼實(shí)現(xiàn)

  public static int gcd(int numA, int numB) {
  
      //如果數(shù)B比數(shù)A大，交換A和B的值，保證A中存放大數(shù)，B中存放小數(shù)
      //A和B值的大小并不影響取余的結(jié)果
      //if(numB > numA) {
      //  numA = numA ^ numB;
      //  numB = numA ^ numB;
      //  numA = numA ^ numB;
      //}
      
      int temp = numA % numB;
      while(temp != 0) {
          numA = numB;
          numB = temp;
          temp = numA % numB;
  }
        
      return numB;
  }
  

1.2.2 遞歸實(shí)現(xiàn)

• 代碼實(shí)現(xiàn)

  public static int gcd(int numA, int numB) {
    
    /*如果數(shù)B比數(shù)A大，交換A和B的值，保證A中存放大數(shù)，B中存放小數(shù)*/
    if(numB > numA) {
        numA = numA ^ numB;
        numB = numA ^ numB;
        numA = numA ^ numB;
    }
    
    int temp = numA % numB;
    if(temp != 0) {
        numB = gcd(numB, temp);
    }
    return numB;
  }
  

1.3 更相減損術(shù)

可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之?！毒耪滤阈g(shù)》

白話譯文：（如果需要對(duì)分?jǐn)?shù)進(jìn)行約分，那么）可以折半的話，就折半（也就是用2來(lái)約分）。如果不可以折半的話，那么就比較分母和分子的大小，用大數(shù)減去小數(shù)，互相減來(lái)減去，一直到減數(shù)與差相等為止，用這個(gè)相等的數(shù)字來(lái)約分。——《百度百科》

先搬出原著古文以及百度百科(時(shí)沒(méi)有看見(jiàn)維基百科的，看來(lái)要找個(gè)時(shí)間給它安排上??)的譯文，不得不佩服古人的智慧。更相減損術(shù)的基本步驟是：對(duì)于這兩個(gè)數(shù)a,b，首先判斷他們是否為偶數(shù)，如果是偶數(shù)，兩者都除以2；如果不是，則用較大的數(shù)a減去較小的數(shù)b，用得到的差temp與較小的數(shù)b進(jìn)行比較，如果相等，則差temp即為最大公約數(shù)；如果不相等，令將小數(shù)b的值賦給大數(shù)a，差temp的值賦給小數(shù)b，即a = b，b = temp。繼續(xù)從頭開(kāi)始執(zhí)行，直到相等時(shí)，temp值乘以約去的2即為最大公約數(shù)。(流程圖待補(bǔ)充)

• 代碼實(shí)現(xiàn)

  /*
   * 更相減損術(shù)中對(duì)2進(jìn)行約分知識(shí)為了簡(jiǎn)化運(yùn)算，不影響最后的結(jié)果，所以代碼省去了對(duì)二的約分。
   */
  public static int gcd(int numA, int numB) {   
    while(numA != numB) {
        if(numA > numB) {
            numA -= numB;
        }else {
            numB -= numA;
        }
    }
    return numA;
  }
  

1.4 算法

2. 最小公倍數(shù)

求最大公約數(shù)的方法我總結(jié)了2種方法：

1. 窮舉法
2. 利用最大公約數(shù)

2.1 窮舉法

• 分析：同樣的最笨也最容易想到的方法，根據(jù)最小公倍數(shù)的定義，只要找出兩個(gè)數(shù)公倍數(shù)中最小的那個(gè)即可。

• 代碼實(shí)現(xiàn)

  public static int lcm(int numA, int numB) {
    if(numB > numA) {
        numA = numA ^ numB;
        numB = numA ^ numB;
        numA = numA ^ numB;
    }
    while(numA % numB != 0) {
        numA += numA;
    }
    return numA;
  }
  

2.2 利用最大公約數(shù)

• 分析：由于最大公約數(shù)和最小公倍數(shù)存在性質(zhì)，兩個(gè)自然數(shù)的乘積等于這兩個(gè)自然數(shù)的最大公約數(shù)和最小公倍數(shù)的乘積。設(shè)這兩個(gè)數(shù)分別為 , ，最大公約數(shù)為 ,最小公倍數(shù)為 ，則有 ，由此可得 ，考慮到可能會(huì)超出數(shù)值范圍，將上述公式改寫(xiě)為 。

• 代碼實(shí)現(xiàn)(注意其中gcd()方法需要實(shí)現(xiàn)，方法見(jiàn)上文)

  public static int lcm(int numA, int numB) {
    return numA / gcd(numA, numB) * numB;   //gcd()方法求最大公約數(shù)
  }
  

3. 參考文章

1. https://blog.csdn.net/Holmofy/article/details/76401074