求最大公约数的四种常用算法（一天一个算法题）

平时拧螺丝，面试造火箭！几乎所有的程序员面试都有这样的困惑，越来越多的大公司会在面试的时候面试算法题，并让你当面写出来。

题目

给你n个数，求出他们的最大公约数g。并且，最少移除多少个数，使得剩下的数的最大公约数大于g。

思考

我们先思考第一个问题，最大公约数，如何求N个数的最大公约数，最简单的算法无非就是枚举X，然后让这N个数都去除以这个X，看看能不能整除，但这种做法真的是太慢了！！

有一个算法叫做辗转相除法，可以求两个数的最大公约数，不过这个题目有多个数字，怎么求这些数字的最大公约数呢？部门不妨假设有3个数a,b,c，用gcd(a,b)表示a跟b的最大公约数，不难想到gcd（a,b,c） = gcd（gcd(a,b), c）。所以我们只要跑一遍辗转相除法，就能够算出一堆数的最大公约数了。

下面是辗转相除法的代码。

接下来我们思考第二个问题，移除最少的数，使得剩余的数的最大公约数比g大。不难想到，剩余的数的最大公约数肯定是g的倍数。（因为g是所有数的公约数，所有数都能整除g.）

紧接着，我们再思考一个问题，假如剩余的数的公约数有2g,4g,6g，我们并不需要考虑是6g大还是2g大，因为能整除6g的数，肯定是能整除2g的数的子集！！

所以我们可以把所有的数，都先去整除g。然后再寻找他们相同的质因数。

最终结果

我们把整个题目拆成3步：

第一步：使用辗转相除法，找到g

第二步：找到比最大数小的所有质数

第三步：判断某个质数最多能被多少个数整除，结果就是数的数量减去最大值。

结语

欢迎大家关注我，后面会推出程序员面试宝典，希望大家都offer Double。

,