go语言找多个数的最大公因数

方法一

func gcd(a,b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a % b)
}

func GetGcd(n []int) int {
	// 先取得Slice中的第一个数, 并假设第一个数为最大公约数
	g := n[0]
	// 依次与Slice中的每个数字求最大公约数
	// 这里i=1, 因为第0个数字已经取出并假设为最大公约数
	for i:=1; i<len(n)-1; i++ {
		oldGcd := g
		// 使用两个数字比较的最大公约数函数进行计算, 得出当前两个数字的最大公约数
		// 循环开始后, 依次将当前最大公约数与后面的数字一一进行运算, 求最大公约数
		g = gcd(g, n[i])
		fmt.Printf("第%d次运算, 当前最大公约数为%d, 与%d运算得出的新最大公约数为: %d \n", i, oldGcd, n[i], g)
	}
	return g
}

更相减损术

更相减损术，举例说明方法如下：

例题：求(4,18,22,16)

取最小的数4,其他的每一个数都与之相减，结果与4组成新的一组数，那么新数组与原数组的最大公因数相等，当出现零以后，排开零对剩下的数进行相同的处理。即：

(4,18,22,16)=(4,14+4,18+4,12+4)=(4,14,18,12)

=(4,10,14,8)=(4,6,10,4)=(4,2,6,0)=(0,2,2,4)=(0,2,0,2)=(0,0,2,0)=2

所以(4,18,22,16)的最大公因数为2.

func multiGcd(arr []int) int {
	
	// 寻找数组最小数
	minFun := func(arr []int) int {
		i := 0
		for idx := range arr {
			if arr[idx] < arr[i] {
				i = idx
			}
		}
		return i
	}
	deleteFromArr := func(min int, arr []int) (ret []int) {
		for i := range arr {
			if arr[i] != min {
				ret = append(ret, arr[i]-min)
			}
		}
		ret = append(ret, min)
		return ret
	}
	ret := 1
	for {
		minIndex := minFun(arr)
		min := arr[minIndex]
		arr = deleteFromArr(min, arr)
		if len(arr) == 1 {
			ret = arr[0]
			break
		}
	}
	return ret
}