部首查漢字
|
拼音查漢字
輾轉相除法
zhǎn zhuǎn xiāng chú fǎ
求兩個正整數的最大公約數的算法。設兩數為a、b(b<a),求它們最大公約數(a、b)的步驟如下:用b除a,得a=bq_1+r_1(0≤r_1<b)。若r_1=0,則(a,b)=b;若r_1≠0,則再用r_1除b,得b=r_1q_2+r_2(0≤r_2<r_1)。若r_2=0,則(a,b)=r_1,若r_2≠0,則繼續用r_2除r_1,……如此下去,直到能整除為止。其最后一個非零余數即為(a,b)。類似地,求兩個多項式的最高公因式也可用此法。
拆分漢字