最大公約數怎么求算法 最大公約數什么意思

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

最大公約數怎么求算法

短除法

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

輾轉相除法

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

最大公約數什么意思

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

最大公因數的性質

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

例如8和9，它們是互質數，所以（8，9）=1，[8，9]=72。

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

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

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

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