最大公約數(shù)怎么求算法 最大公約數(shù)什么意思

求最大公約數(shù)有多種方法，常見的有質(zhì)因數(shù)分解法、短除法、輾轉(zhuǎn)相除法、更相減損法。把每個數(shù)分別分解質(zhì)因數(shù)，然后找出相同的質(zhì)因數(shù)，最后將這些相同的質(zhì)因數(shù)相乘得到最大公約數(shù)。

最大公約數(shù)怎么求算法

短除法

在求兩個數(shù)的最大公約數(shù)時，如果無法進行質(zhì)因數(shù)分解，可以采用短除法。短除法的步驟如下：將除數(shù)除以被除數(shù)得到商，然后用除數(shù)除以商得到余數(shù)，再用余數(shù)去除除數(shù)，如此反復(fù)，直到余數(shù)為零為止。最后將所有的除數(shù)相乘，得到的積即為最大公約數(shù)。

輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法是一種簡單的求最大公約數(shù)的方法，其基本思想是：用較大的數(shù)除以較小的數(shù)得到商和余數(shù)，再用較小的數(shù)除以商得到新的商和余數(shù)，如此反復(fù)，直到余數(shù)為零為止。最后得到的積即為最大公約數(shù)。

最大公約數(shù)什么意思

最大公因數(shù)，也稱最大公約數(shù)、最大公因子，指兩個或多個整數(shù)共有約數(shù)中最大的一個。a，b的最大公約數(shù)記為（a，b），同樣的，a，b，c的最大公約數(shù)記為（a，b，c），多個整數(shù)的最大公約數(shù)也有同樣的記號。求最大公約數(shù)有多種方法，常見的有質(zhì)因數(shù)分解法、短除法、輾轉(zhuǎn)相除法、更相減損法。與最大公約數(shù)相對應(yīng)的概念是最小公倍數(shù)，a，b的最小公倍數(shù)記為[a，b]。

最大公因數(shù)的性質(zhì)

（1）如果兩個自然數(shù)是互質(zhì)數(shù)，那么它們的最大公約數(shù)是1，最小公倍數(shù)是這兩個數(shù)的乘積。

例如8和9，它們是互質(zhì)數(shù)，所以（8，9）=1，[8，9]=72。

（2）如果兩個自然數(shù)中，較大數(shù)是較小數(shù)的倍數(shù)，那么較小數(shù)就是這兩個數(shù)的最大公約數(shù)，較大數(shù)就是這兩個數(shù)的最小公倍數(shù)。

例如18與3，18÷3=6，所以（18，3）=3，[18，3]=18。

（3）兩個整數(shù)分別除以它們的最大公約數(shù)，所得的商是互質(zhì)數(shù)。

例如8和14分別除以它們的最大公約數(shù)2，所得的商分別為4和7，那么4和7是互質(zhì)數(shù)。