求兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù),輾轉(zhuǎn)相除法算法如何理解

數(shù)學(xué)人氣：984 ℃時(shí)間：2020-04-03 05:52:27

優(yōu)質(zhì)解答

大數(shù)為max,小數(shù)為min.用大數(shù)除以小數(shù)取余數(shù)（rest),因?yàn)橛鄶?shù)(rest）不可能大于被除數(shù)（min）,所以可以把min當(dāng)成大數(shù),rest當(dāng)成小數(shù),繼續(xù)相除.直到余數(shù)為0,這個(gè)時(shí)候max和rest是相等的,都是最大公約數(shù).
最小公倍數(shù)是兩數(shù)之積除以最大公約數(shù)