快评
gcd（最大公约数）是算法入门问题，难度属于课后作业的水平，但确是很经典的。切记不要使用蛮力遍历，大数BigInt下辗转相除法+位运算可以得到不错的速度提升，但是非BigInt大数据量下辗转相除法资源消耗更小更快。
对于存在大素数的情况，可以参考Stein算法:
欧几里德算法是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。
考虑现在的硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。 （注：说到抛弃除法和取模，其实辗转相除法可以写成减法的形式)
Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法 算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。
为了说明Stein算法的正确性，首先必须注意到以下结论：
gcd(a,a) = a，也就是一个数和他自身的公约数是其自身
gcd(ka,kb) = k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除。
有了上述规律就可以给出Stein算法如下：
如果A=0，B是最大公约数，算法结束
如果B=0，A是最大公约数，算法结束
设置A1 = A、B1=B和C1 = 1
如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)
如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很显然啦，2不是奇数的约数)
如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很显然啦，2不是奇数的约数)
如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn
n++，转4
这个算法的原理很显然，不再证明了。
解题思路
非大数，小数据量下辗转相除法相对辗转相除法更快一些。
代码
// 辗转相除法+位运算
// func gcd(n1 int, n2 int) int{
// factor := 1
// if n1&1 == 0 && n2&1 == 0{
// n1=n1>>1
// n2=n2>>1
// factor=2
// }else{
// if n1&1 == 0{ // 偶数
// n1=n1>>1
// }
// if n2&1 == 0{
// n2=n2>>1
// }
// }
// if n1>n2{
// res := n1-n1/n2*n2
// if res == 0{
// return factor*n2
// }
// return factor*gcd(n2, res)
// }else{
// res := n2-n2/n1*n1
// if res == 0{
// return factor*n1
// }
// return factor*gcd(n1, res)
// }
// }
// 辗转相减法+位运算
func gcd(n1 int, n2 int) int{
factor := false
if n1&1 == 0 && n2&1 == 0{
n1=n1>>1
n2=n2>>1
factor=true
}else{
if n1&1 == 0{ // 偶数
n1=n1>>1
}
if n2&1 == 0{
n2=n2>>1
}
}
if n1==n2{
if factor{
return n1*2
}
return n1
}
if n1>n2{
if factor{
return gcd(n1-n2, n2)*2
}
return gcd(n1-n2, n2)
}else{
if factor{
return gcd(n2-n1, n1)*2
}
return gcd(n2-n1, n1)
}
}
func findGCD(nums []int) int {
if len(nums)==2{
if nums[0]>nums[1]{
return gcd(nums[0], nums[1])
}else{
return gcd(nums[1], nums[0])
}
}
min := nums[0]
max := nums[0]
for _, n := range nums{
if n<min{
min = n
}else if n>max{
max = n
}
}
return gcd(max, min)
}
留言