基本概念

• 因數(shù) ：若A=m×n扑浸，則稱m，n是A的因數(shù)燕偶；A是m喝噪，n的倍數(shù) 一個(gè)數(shù)的最大因數(shù)和最小倍數(shù)都是它本身
  一個(gè)數(shù)的最小因數(shù)是1。
• 質(zhì)數(shù)（素?cái)?shù)）：在大于1的整數(shù)中指么，只有1和它本身兩個(gè)因數(shù)的數(shù)酝惧，叫做質(zhì)數(shù)。** 0伯诬、1既不是質(zhì)數(shù)也不是合數(shù)晚唇；2 是唯一的偶數(shù)質(zhì)數(shù)**。
• 約數(shù)：若A÷B=x?0（A能夠整除B盗似，沒(méi)有余數(shù)）哩陕； 則稱B是A的約數(shù)；A是B的倍數(shù)
• 質(zhì)約數(shù)：如果一個(gè)整數(shù)的約數(shù)恰好是一個(gè)質(zhì)數(shù)赫舒，則稱此約數(shù)為這個(gè)整數(shù)的質(zhì)約數(shù)
• 分解質(zhì)因數(shù)（分解質(zhì)約數(shù)）：把一個(gè)整數(shù)分解成多個(gè)質(zhì)因數(shù)（約數(shù)）連乘 標(biāo)準(zhǔn)分解質(zhì)因數(shù)的寫法：把小的寫在前面悍及，多個(gè)相同的質(zhì)數(shù)要用乘方表示。

宣傳語(yǔ)

歷經(jīng)兩個(gè)半月的準(zhǔn)備接癌，三次大改版心赶，十七次小改版。le1024終于要和大家見(jiàn)面了缺猛。

le1024每天推薦1~3段缨叫，有趣、有愛(ài)枯夜、有故事的視頻弯汰。

為您工作、學(xué)習(xí)湖雹、生活之余增加一點(diǎn)快樂(lè)的感覺(jué)咏闪。

• 互質(zhì), 也稱之為互素。若N個(gè)整數(shù)的最大公因子是1摔吏，則稱這N個(gè)整數(shù)互質(zhì)鸽嫂。

• 合數(shù)：在大于2的整數(shù)中，除了1和它本身兩個(gè)因數(shù)征讲，還有其它因數(shù)的數(shù)据某，叫做合數(shù)
  整數(shù)a除以整數(shù)b(b≠0) 除得的商正好是整數(shù)而沒(méi)有余數(shù)，我們就說(shuō)a能被b整除诗箍，或b能整除a癣籽。a叫b的倍數(shù)，b叫a的約數(shù)（或 因數(shù)）。一個(gè)數(shù)的約數(shù)是有限的筷狼。

什么是最大公約數(shù)

最大公約數(shù)瓶籽，也稱最大公因數(shù)、最大公因子埂材，指兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)塑顺。
如，12 和 30 的約數(shù)俏险，以及公有的約數(shù)严拒。

那么可知，12和30的最大公約數(shù)為6

輾轉(zhuǎn)相除法

兩個(gè)整數(shù)的最大公約數(shù)是能夠同時(shí)整除它們的最大的正整數(shù)竖独。輾轉(zhuǎn)相除法基于如下原理：兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)的相除余數(shù)的最大公約數(shù) 裤唠。

例如，252和105的最大公約數(shù)是21（252 = 21 × 12预鬓；105 = 21 × 5）巧骚；因?yàn)?52 / 105 = 2余42，所以105和42的最大公約數(shù)也是21格二。在這個(gè)過(guò)程中劈彪，較大的數(shù)縮小了，所以繼續(xù)進(jìn)行同樣的計(jì)算可以不斷縮小這兩個(gè)數(shù)直至余數(shù)變?yōu)榱愣ゲ隆＿@時(shí)的除數(shù)就是所求的兩個(gè)數(shù)的最大公約數(shù)沧奴。

輾轉(zhuǎn)相除法的演示動(dòng)畫(huà)：兩條線段分別表示252和105，其中每一段表示21长窄。動(dòng)畫(huà)演示了循環(huán)從大數(shù)中減去小數(shù)滔吠，直到其中一段的長(zhǎng)度為0，此時(shí)剩下的一條線段的長(zhǎng)度就是252和105的最大公約數(shù)挠日。

條形表示法：

最初的綠色矩形的長(zhǎng)和寬分別是a = 1071疮绷、b = 462，從中不斷鋪上462×462的正方形直到剩下部分面積是462×147嚣潜；然后再鋪上147×147的正方形直至剩下21×147的面積冬骚；最后，鋪上21×21的正方形時(shí)懂算，綠色部分就沒(méi)有了只冻。即21是1071和462的最大公約數(shù).

瓷磚表示法：

數(shù)學(xué)表示：

f(x,y) = f(y, x % y)

ruby 代碼：

def gcd(x , y)
    return (y == 0 )? x : gcd(y , x % y)
end

用輾轉(zhuǎn)相除法求幾個(gè)數(shù)的最大公約數(shù)，可以先求出其中任意兩個(gè)數(shù)的最大公約數(shù)计技，再求這個(gè)最大公約數(shù)與第三個(gè)數(shù)的最大公約數(shù)喜德，依次求下去，直到最后一個(gè)數(shù)為止垮媒。最后所得的那個(gè)最大公約數(shù)舍悯，就是所有這些數(shù)的最大公約數(shù)航棱。

時(shí)間復(fù)雜度：
O(log n），其中 n 為輸入數(shù)值的位數(shù)贱呐。

相減法

以較大的數(shù)減較小的數(shù)丧诺，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)奄薇。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止抗愁。

例如：91和49

數(shù)學(xué)表示：

f(x,y) = f(x-y, y)

ruby 代碼：

def gcd2(x , y)
  if(x < y)
    return  gcd2(y , x)
  elsif(y == 0)
    return x
  else
    return gcd2(x - y , y)
  end
end

時(shí)間復(fù)雜度： < O(log n）

此解法用減法而不是除法馁蒂，降低了計(jì)算的復(fù)雜度，但是迭代的次數(shù)比除法要多蜘腌，當(dāng)遇到f(10000000,1)的情況時(shí)這不是一個(gè)好方法沫屡。

相除法和想減法的區(qū)別

（1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主撮珠，更相減損術(shù)以減法為主沮脖，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯芯急。
（2）從結(jié)果體現(xiàn)形式來(lái)看勺届，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到娶耍。

融合以上兩種方式

首先免姿，從公約數(shù)的特點(diǎn)入手

• x和y來(lái)說(shuō)，如果 x = k * x1 , 那么y = k * y1 ,那么就有f(x, y) = k * f(x1, y1)
• 如果x = p * x1, 假設(shè)p是素?cái)?shù)榕酒，并且y % p!=0 (即y不能被p整除, 若等于0胚膊，那么y就是最大公約數(shù))，那么f(x, y) = f(p * x1, y) = f(x1, y)
• 2是一個(gè)素?cái)?shù)想鹰，同時(shí)對(duì)于二進(jìn)制表示的大整數(shù)而言紊婉，可以很容易地除以2和乘以2的運(yùn)算轉(zhuǎn)換成移位運(yùn)算，從而避免大整數(shù)除法辑舷，由此可以利用2這個(gè)數(shù)字來(lái)進(jìn)行分析

數(shù)學(xué)的表示方法

取 p = 2  
若x, y 均為偶數(shù) f(x,y)= 2 * f(x/2,y/2) = 2 * f(x >> 1, y>>1)  
若x為偶數(shù)喻犁，y為奇數(shù) f(x,y) = f(x/2, y) = f(x >> 1, y)  
若x為奇數(shù)，y為偶數(shù) f(x,y) = f(x, y/2) = f(x, y >> 1)  
若x, y均為奇數(shù)  f(x, y) = f(y, x-y)
那么在f(x,y) = f(y, x- y)之后惩妇，(x - y)是一個(gè)偶數(shù)株汉，下一步就是除以2的操作   

ruby 代碼

  def gcd3(x ,y)
    if(x < y)
      return gcd3(y, x)
    end

    if(y == 0)
      return x
    else
      if(is_even?(x))
        if (is_even?(y))
          return (gcd3(x >> 1, y >> 1) << 1)
        else
          return gcd3(x >> 1, y)
        end
      else
        if(is_even?(y))
          return gcd3(x, y >> 1)
        else
          return gcd3(y, x-y)
        end
      end
    end
  end

  def is_even?(a)
    if(a%2 == 0)
      return true
    else
      return false
    end
  end

時(shí)間復(fù)雜度

O(log2(max(x,y)))

附

輾轉(zhuǎn)相除法證明：

設(shè)兩數(shù)為a、b(b<a）歌殃，用gcd(a,b）表示a乔妈，b的最大公約數(shù)，r=a mod b 為a除以b以后的余數(shù)，k為a除以b的商住拭，即a÷b=k.......r。輾轉(zhuǎn)相除法即是要證明gcd(a,b)=gcd(b,r）谒养。

第一步：令c=gcd(a,b）股淡，則設(shè)a=mc身隐，b=nc
第二步：根據(jù)前提可知r =a-kb=mc-knc=(m-kn)c
第三步：根據(jù)第二步結(jié)果可知c也是r的因數(shù)
第四步：可以斷定m-kn與n互素【否則，可設(shè)m-kn=xd唯灵，n=yd贾铝，（d>1），則m=kn+xd=kyd+xd=(ky+x)d埠帕，則a=mc=(ky+x)dc垢揩，b=nc=ycd，故a與b最大公約數(shù)成為cd敛瓷，而非c叁巨，與前面結(jié)論矛盾】
從而可知gcd(b,r)=c，繼而gcd(a,b)=gcd(b,r）呐籽。