最大公因數與最小公倍數-gcd&lcm

一、一些性質

　　 \(gcd(a,b)=gcd(b,a)\)

　　 \(gcd(-a,b)=gcd(a,b)\)

　　 \(gcd(a,a)=|a|, gcd(a,0)=|a|\)

　　 \(gcd(a,1)=1\)

　　 \(gcd(a,b)=gcd(b, a mod b)\)

　　 \(gcd(a,b)=gcd(b, a-b)\)

　　 \(gcd(a,b)*lcm(a,b)=ab\)

　　 \(a|t,b|t⇒lcm(a,b)\)

　　 \(...\)

二、最大公約數-gcd

1.歐幾裡得輾轉相除法

證明：

　　 設\(a=qb+r\)，\(d|a\)且\(d|b\),

　　 \(∵a=qb+r,\)

　　 \(∴r=a-qb,\)

　　 \(∵d|a\)且\(d|b\)

　　 \(∴d | a -qb\)

　　 \(∴d | r\)

　　 \(∴a,b\)的公因數都是\(b,r\)的公因數

　　 \(∴gcd(a,b)=gcd(b,r)\)

代碼實作：

int gcd(int a, int b){
  return b == 0 ? a : gcd(b , a % b);          
}
      

2.stein_gcd算法

int stein(int a, int b) {
  if (a == 0) return b;
  if (b == 0) return a;
  if (a % 2 == 0 && b % 2 == 0) return stein(a >> 1, a >> 1) * 2;  //當兩數均為偶數時将其同時除以2至至少一數為奇數為止，記錄除掉的所有公因數2的乘積k
  else if (a % 2 == 0) return stein(a >> 1, b);  //因為隻有一個數含有2作為因數，是以除以2後gcd(a,b)不變
  else if (b % 2 == 0) return stein(a, b >> 1);  //同上
  else return stein(abs(a - b), min(a, b));   //詳情請檢視'更相減損數'                              
}
      

三、最小公倍數-lcm

基于gcd(a,b)*lcm(a,b)=ab這條性質則可求出最小公倍數
      

好像stein算法不是很常用，但的确彌補了歐幾裡得算法的一些缺點