c語言最大公約數(shù)的求法
回答
愛揚(yáng)教育
2022-02-07
- 相關(guān)推薦
窮舉法（枚舉法）：
從兩個(gè)數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù)。
更相減損法：
Steps：任意給定兩個(gè)正整數(shù)；判斷它們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是則執(zhí)行第二步。
擴(kuò)展資料
以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止。
則第一步中約掉的若干個(gè)2與第二步中等數(shù)的乘積就是所求的最大公約數(shù)。
輾轉(zhuǎn)相除法（歐幾里德法）：
C語言中用于計(jì)算兩個(gè)正整數(shù)a,b的最大公約數(shù)，采用函數(shù)嵌套調(diào)用形式進(jìn)行求兩個(gè)數(shù)的最大公約數(shù)。其算法過程為：
前提：設(shè)兩數(shù)為a,b設(shè)其中a做被除數(shù),b做除數(shù),temp為余數(shù)
Steps:大數(shù)放a中，小數(shù)放b中；
求a/b的余數(shù)；
若temp=0則b為最大公約數(shù)；
如果temp!=0則把b的值給a,temp的值給a；
返回第二步。