最大公約數(shù)和最小公倍數(shù)是我們小學學習的犀呼，那時候我們求最大公約數(shù)抡驼，往往是將兩數(shù)的所有約數(shù)全部列出來争占，然后找出共有的約數(shù)中其中最大的那個砰盐；而求最小公倍數(shù)也往往是將兩數(shù)的倍數(shù)一一列出闷袒，找出相等的倍數(shù)中最小的那個。

好吧??岩梳，原諒我的無知囊骤。。冀值。原來還可以用短除法求最大公約數(shù)和最小公倍數(shù)也物，小學白學了??，一直窮舉窮舉了六年列疗，我枯了??滑蚯。

短除法

最小公倍數(shù)：

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

1. 最大公約數(shù)

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

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

下面分別講解：

1.1 窮舉法

• 分析：窮舉法是最笨告材，但是最容易想到的方法??。根據(jù)定義古劲，我們只需找出一個數(shù)能同時被兩個數(shù)整除斥赋，且為此類數(shù)中最大的一個即可。取兩個數(shù)中較小的數(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)相除法，又名歐幾里得算法缚窿，其基本原理： 兩個整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù) 棘幸。一看這基本原理是不是激動了一下??，又可以用遞歸了倦零。下面給出遞歸和非遞歸的兩種實現(xiàn)误续。具體介紹詳見維基百科

維基百科錯誤

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

1.2.1 非遞歸實現(xiàn)

• 分析：取這兩個數(shù)腺办，將大數(shù)放在numA中焰手，小數(shù)放在numB中，求numA除以numB的余數(shù)怀喉，放在temp中书妻，根據(jù)輾轉(zhuǎn)相除法(歐幾里得算法)，兩個整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)躬拢。如果余數(shù)temp不為 躲履，一直循環(huán)將numB值賦給numA，temp值賦給numB估灿，再對numA和numB求余崇呵，直到余數(shù)temp為 ，則此時numB為最大公約數(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 遞歸實現(xiàn)

• 代碼實現(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ù)

可半者半之叠骑，不可半者，副置分母削茁、子之數(shù)宙枷，以少減多，更相減損茧跋，求其等也慰丛。以等數(shù)約之●迹——《九章算術(shù)》

白話譯文：（如果需要對分數(shù)進行約分诅病，那么）可以折半的話，就折半（也就是用2來約分）粥烁。如果不可以折半的話贤笆，那么就比較分母和分子的大小，用大數(shù)減去小數(shù)讨阻，互相減來減去芥永，一直到減數(shù)與差相等為止，用這個相等的數(shù)字來約分钝吮÷窠В——《百度百科》

先搬出原著古文以及百度百科(時沒有看見維基百科的贴唇，看來要找個時間給它安排上??)的譯文，不得不佩服古人的智慧飞袋。更相減損術(shù)的基本步驟是：對于這兩個數(shù)a,b，首先判斷他們是否為偶數(shù)链患，如果是偶數(shù)巧鸭，兩者都除以2；如果不是麻捻，則用較大的數(shù)a減去較小的數(shù)b纲仍，用得到的差temp與較小的數(shù)b進行比較，如果相等贸毕，則差temp即為最大公約數(shù)郑叠；如果不相等，令將小數(shù)b的值賦給大數(shù)a明棍，差temp的值賦給小數(shù)b乡革，即a = b，b = temp摊腋。繼續(xù)從頭開始執(zhí)行沸版，直到相等時，temp值乘以約去的2即為最大公約數(shù)兴蒸。(流程圖待補充)

• 代碼實現(xiàn)

  /*
   * 更相減損術(shù)中對2進行約分知識為了簡化運算视粮，不影響最后的結(jié)果，所以代碼省去了對二的約分橙凳。
   */
  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ù)的定義，只要找出兩個數(shù)公倍數(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ì)钓觉，兩個自然數(shù)的乘積等于這兩個自然數(shù)的最大公約數(shù)和最小公倍數(shù)的乘積。設(shè)這兩個數(shù)分別為 , 值戳，最大公約數(shù)為 ,最小公倍數(shù)為 议谷，則有 ，由此可得 堕虹，考慮到可能會超出數(shù)值范圍卧晓，將上述公式改寫為 。

• 代碼實現(xiàn)(注意其中gcd()方法需要實現(xià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