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

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

题目

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

求最大公约数的四种常用算法(一天一个算法题)(1)

思考

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

求最大公约数的四种常用算法(一天一个算法题)(2)

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

求最大公约数的四种常用算法(一天一个算法题)(3)

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

求最大公约数的四种常用算法(一天一个算法题)(4)

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

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

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

求最大公约数的四种常用算法(一天一个算法题)(5)

最终结果

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

第一步:使用辗转相除法,找到g

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

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

结语

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

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页