兩個數的最大公約數

• 1.輾轉相除法求解兩個數的最大公約數
• 2.更相減損術求解兩個數的最大公約數
• 3.不嚴格理解

1.輾轉相除法求解兩個數的最大公約數

輾轉相除法：兩個正整數a和b（a>b）的最大公約數等于a除以b的余數與b 之間的最大公約數。–如果a能被b整除，那么a和b之間的最大公約數為b.

def gcd(a,b):while(a%b!=0):m=a%ba=bb=mreturn b

2.更相減損術求解兩個數的最大公約數

更相減損術：兩個正整數a和b（a>b）的最大公約數等于a-b的差值c和b的最大公約數。

def gcd(a,b):while(a!=b):c=a-ba=max(c,b)b=min(c,b)return b

3.不嚴格理解

更相減損術原理講解，參看博文：http://blog.sina.com.cn/s/blog_5253930a0102y5p8.html

輾轉相除法原理:
1.假設$a=b?k+r$
2.將b拆成最小因數相乘:$n=c?d?e$,那么$a=k?c?d?e+r$
3.如果r是b的因數，則b中有一個或多個因數乘積可構成r,假設r=c*d
4.$a=k?c?d?e+r=k?c?d?e+c?d=c?d(k?e+1)$,則r也為a的因數
5.因為$(k?e+1)$與$k?e$是相鄰的兩個數，沒有除了1之外的公約數，所以a和b的最大公約數為r

綜上就是通過不斷的相除，找到是b因數的r.

總結

以上是生活随笔為你收集整理的算法(9)--两个数的最大公约数的全部內容，希望文章能夠幫你解決所遇到的問題。

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