#3

段夢超2009-12-20 21:31

輸入兩個正整數(shù)m和n, 求其最大公約數(shù)和最小公倍數(shù). <1> 用輾轉(zhuǎn)相除法求最大公約數(shù) 算法描述: m對n求余為a, 若a不等于0 則 m 最小公倍數(shù) = 兩個數(shù)的積 / 最大公約數(shù)

#include int main()

{

int m, n; int m_cup, n_cup, res; /*被除數(shù), 除數(shù), 余數(shù)*/

printf("Enter two integer:\n");

scanf("%d %d", &m, &n);

if (m > 0 && n >0)

{

m_cup = m;

n_cup = n;

res = m_cup % n_cup;

while (res != 0)

{

m_cup = n_cup;

n_cup = res;

res = m_cup % n_cup;

}

printf("Greatest common divisor: %d\n", n_cup);

printf("Lease common multiple : %d\n", m * n / n_cup);

}

else printf("Error!\n");

return 0;

}

★ 關(guān)于輾轉(zhuǎn)相除法, 搜了一下, 在我國古代的《九章算術(shù)》中就有記載，現(xiàn)摘錄如下: 約分術(shù)曰：“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。” 其中所說的“等數(shù)”，就是最大公約數(shù)。求“等數(shù)”的辦法是“更相減損”法，實際上就是輾轉(zhuǎn)相除法。 輾轉(zhuǎn)相除法求最大公約數(shù)，是一種比較好的方法，比較快。 對于52317和75569兩個數(shù)，你能迅速地求出它們的最大公約數(shù)嗎？一般來說你會找一找公共的使因子，這題可麻煩了，不好找，質(zhì)因子大。 現(xiàn)在教你用輾轉(zhuǎn)相除法來求最大公約數(shù)。 先用較大的75569除以52317，得商1，余數(shù)23252，再以52317除以23252，得商2，余數(shù)是5813，再用23252做被除數(shù)，5813做除數(shù)，正好除盡得商數(shù)4。這樣5813就是75569和52317的最大公約數(shù)。你要是用分解使因數(shù)的辦法，肯定找不到。 那么，這輾轉(zhuǎn)相除法為什么能得到最大公約數(shù)呢？下面我就給大伙談?wù)劇?比如說有要求a、b兩個整數(shù)的最大公約數(shù)，a＞b，那么我們先用a除以b，得到商8，余數(shù)r1：a÷b＝q1…r1我們當(dāng)然也可以把上面這個式子改寫成乘法式：a＝bq1＋r1------l) 如果r1＝0，那么b就是a、b的最大公約數(shù)3。要是r1≠0，就繼續(xù)除，用b除以r1，我們也可以有和上面一樣的式子： b＝r1q2＋r2-------2) 如果余數(shù)r2＝0，那么r1就是所求的最大公約數(shù)3。為什么呢？因為如果2)式變成了b＝r1q2，那么b1r1的公約數(shù)就一定是a1b的公約數(shù)。這是因為一個數(shù)能同時除盡b和r1，那么由l)式，就一定能整除a，從而也是a1b的公約數(shù)。 反過來，如果一個數(shù)d，能同時整除a1b，那么由1)式，也一定能整除r1，從而也有d是b1r1的公約數(shù)。 這樣，a和b的公約數(shù)與b和r1的公約數(shù)完全一樣，那么這兩對的最大公約數(shù)也一定相同。那b1r1的最大公約數(shù)，在r1＝0時，不就是r1嗎？所以a和b的最大公約數(shù)也是r1了。 有人會說，那r2不等于0怎么辦？那當(dāng)然是繼續(xù)往下做，用r1除以r2，……直到余數(shù)為零為止。 在這種方法里，先做除數(shù)的，后一步就成了被除數(shù)，這就是輾轉(zhuǎn)相除法名字的來歷吧。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的C语言求35 45的最大公约数,C语言怎么求最大公约数和最小公倍数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。