最大公约数什么意思

公约数，亦称“公因数”。它是指能同时整除几个整数的数。如果一个整数同时是几个整数的约数，称这个整数为它们的“公约数”。

最大公约数什么意思？

最大公约数，简称最大公因数，指两个或多个整数共有约数中最大的一个。

a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。

例如：12、16的公约数有1、2、4，其中4就是12、16的最大公约数。

最大公约数求解方法

1、朴素算法：从m、n较小的一个数开始枚举，如果都能被m、n整除，那么该数就是两数的最大公约数，否则继续减一，直至枚举到1为止。（这个算法复杂度十分不优秀，只是帮助大家理解如何求最大公约数，彰显辗转相除算法的优秀）。

例如：求12、8的最大公约数

 解：先枚举

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

因此最大公约数为4。

例1 ：求两个正整数ｍ，ｎ的最大公约数。

求任意两个自然数m和n的最大公约数，可以想到其最大的可能就是两个数中的较小者min，最小可能是1。

所以，可以设最大公约数gcd从min开始进行判断，若gcd>1并且没有同时整除m和n，那么就gcd-1，重复判断是否整除。

例2 ：18和24的公约数有2，3，6三个，其中以6为最大，6就是18和24的最大公约数。

两个或两个以上数的几个公约数中最大的一个公约数。

12和6的公约数2与3中,3是最大公约数。

任意两数的最大公约数如何计算？

任意两个自然数共有的约数叫这两个数的公约数。公约数中最大的叫这两个数的最大公约数。求两个数的最大公约数的方法一般有三种。

一、短除。

比方说求45与48的最大公约数，都除以3，商分别是9、16，这两个数互质，所以它们的最大公约数数3。

二、分解质因数的方法。

45=3×3×5，48=2×2×2×2×3，那么最大公约数是3。

三、辗转相除法这里不举例。