公約數(shù)，亦稱“公因數(shù)”。它是指能同時整除幾個整數(shù)的數(shù)。如果一個整數(shù)同時是幾個整數(shù)的約數(shù)，稱這個整數(shù)為它們的“公約數(shù)”。

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

最大公約數(shù)，簡稱最大公因數(shù)，指兩個或多個整數(shù)共有約數(shù)中最大的一個。

a，b的最大公約數(shù)記為（a，b），同樣的，a，b，c的最大公約數(shù)記為（a，b，c），多個整數(shù)的最大公約數(shù)也有同樣的記號。

例如：12、16的公約數(shù)有1、2、4，其中4就是12、16的最大公約數(shù)。

最大公約數(shù)求解方法

1、樸素算法：從m、n較小的一個數(shù)開始枚舉，如果都能被m、n整除，那么該數(shù)就是兩數(shù)的最大公約數(shù)，否則繼續(xù)減一，直至枚舉到1為止。（這個算法復雜度十分不優(yōu)秀，只是幫助大家理解如何求最大公約數(shù)，彰顯輾轉相除算法的優(yōu)秀）。

例如：求12、8的最大公約數(shù)

 解：先枚舉

8 12/8=1......4 8/8=1......0

7 12/7=1......5 8/7=1......1

6 12/6=2......0 8/6=1......2

5 12/5=2......2 8/5=1......3

4 12/4=3......0 8/4=2......0

因此最大公約數(shù)為4。

例1 ：求兩個正整數(shù)ｍ，ｎ的最大公約數(shù)。

求任意兩個自然數(shù)m和n的最大公約數(shù)，可以想到其最大的可能就是兩個數(shù)中的較小者min，最小可能是1。

所以，可以設最大公約數(shù)gcd從min開始進行判斷，若gcd>1并且沒有同時整除m和n，那么就gcd-1，重復判斷是否整除。

例2 ：18和24的公約數(shù)有2，3，6三個，其中以6為最大，6就是18和24的最大公約數(shù)。

兩個或兩個以上數(shù)的幾個公約數(shù)中最大的一個公約數(shù)。

12和6的公約數(shù)2與3中,3是最大公約數(shù)。

任意兩數(shù)的最大公約數(shù)如何計算？

任意兩個自然數(shù)共有的約數(shù)叫這兩個數(shù)的公約數(shù)。公約數(shù)中最大的叫這兩個數(shù)的最大公約數(shù)。求兩個數(shù)的最大公約數(shù)的方法一般有三種。

一、短除。

比方說求45與48的最大公約數(shù)，都除以3，商分別是9、16，這兩個數(shù)互質(zhì)，所以它們的最大公約數(shù)數(shù)3。

二、分解質(zhì)因數(shù)的方法。

45=3×3×5，48=2×2×2×2×3，那么最大公約數(shù)是3。

三、輾轉相除法這里不舉例。