求最大公因數的三種算法及簡要說明

1、連續整數法

從給定的最小的數開始按1遞減，直至找到一個能被兩者都整除的數。 public static int gcd1(int x, int y){int min = Math.min(x,y);while (x%min!=0|| y%min!=0){min--;}return min;}

2、輾轉相除法

也叫歐幾里得算法，兩個整數的最大公約數等于其中較小的那個數和兩數相除余數的最大公約數

證明：
假設正整數a>b，有a = kb + r（k，r皆為正整數，且r<b）
假設存在正整數d為a和b的公因數，即d|a,d|b.
而r = a - kb=a mod b，兩邊同時除以d，r/d=a/d-kb/d=m，由等式右邊可知m為整數，
因此d|r
因此d也是b,a mod b的公約數。
因(a,b)和(b,a mod b)的公約數相等，則其最大公約數也相等.QED.

public static int gcd(int m,int n) {if(m<n) { // guarantee m > nint k=m;m=n;n=k;}return m%n == 0?n:gcd(n,m%n);}

3、更相減損法

兩個奇數的最大公約數等于兩者之和的一半與兩者之差的一半的最大公約數，從而減小兩個數之間的差值，直到逼近為一個數，即最大公約數。

證明：gcd（a,b）= gcd ((a+b)/2,(a-b)/2) , a,b都為奇數

設 a = md , b = nd, d = gcd(a,b), m, n, d 都為奇數
(a+b)/2 = (m+n)/2d, (a-b)/2 = (m-n)/2d。兩者都為d的整數倍
且倍數不同時為偶數（反證法易證）。QED。

public static int gcd3(int m, int n){if(m<n) { // guarantee m > nint k=m;m=n;n=k;}if(m==n){return m;}if(m%2==0&&n%2==0){return 2*gcd3(m/2,n/2);}if(m%2==0){return gcd3(m/2,n);}if(n%2==0){return gcd3(m,n/2);}else{return gcd3((m+n)/2,(m-n)/2);}}

總結

以上是生活随笔為你收集整理的求最大公因数的三种算法及简要说明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。