輾轉(zhuǎn)相除法原理是設(shè)兩數(shù)為a、b(a>b)，用gcd(a，b)表示a，b的最大公約數(shù)，r=a(modb)為a除以b的余數(shù)，k為a除以b的商，即a÷b=k.......r 。輾轉(zhuǎn)相除法即是要證明gcd(a，b)=gcd(b，r) 。
輾轉(zhuǎn)相除法，又名歐幾里德算法（Euclideanalgorithm）乃求兩個(gè)正整數(shù)之最大公因子的算法 。它是已知最古老的算法，其可追溯至公元前300年前 。
【輾轉(zhuǎn)相除法原理】設(shè)兩數(shù)為a、b(a>b)，求a和b最大公約數(shù)(a，b)的步驟如下：用a除以b，得a÷b=q......r1(0≤r1) 。若r1=0，則(a，b)=b；若r1≠0，則再用b除以r1，得b÷r1=q......r2 (0≤r2）.若r2=0，則(a，b)=r1，若r2≠0，則繼續(xù)用r1除以r2，……如此下去，直到能整除為止 。其最后一個(gè)余數(shù)為0的除數(shù)即為(a,b)的最大公約數(shù) 。
推薦閱讀
- 人的體溫早晚相差多少
- 一天早晚體重相差多少正常
- 原神的無(wú)相之雷怎么打
- b站封面圖片怎么提取
- b站會(huì)員購(gòu)訂單怎么退款
- 12屬相十二生肖 01的屬什么生肖
- 抖音隨拍添加字幕的圖文操作
- 如愿以償相近的成語(yǔ)
- 軟件靜態(tài)測(cè)試方法
- QQ空間寵物怎么得第二只