005. 最小公倍数(smallest multiple)

2520是可以被从一到十所有自然数整除的最小的数,即为从一到十的自然数的最小公倍数,求从一到二十所有自然数的最小公倍数。

分析:这道题至少有两种解题思路,第一种思路是编写一个计算最小公倍数的函数,然后对一至二十的所有整数求最小公倍数。在python的math库中有一个计算最大公约数的函数,我们可以根据欧几里德公式,从两个数最大公约数推出两个数的最小公倍数,即对于任意自然数\(a,b\),设两个数的最大公约数为\(gcd(a,b)\),则两个数的最小公倍数

$$ lcm(a,b)=\frac{ab}{gcd(a,b)} $$

据此,我们可以先求出两个数的最小公倍数,再用这个最小公倍数与第三个数求最小公倍数,这里可以利用reduce()函数迭代求出多个数的最小公倍数。这种思路在问题规模较小时表现良好,对题目中的问题也可以在几微秒内给出答案。但是我们可以更深入的分析问题,可以发现一种更为高效的方法。

我们来看一个简化的问题,题目中说一到十的所有整数的最小公倍数是2520,这个数可以如何求出来?我们先对二到十的所有数进行质因数分解,结果如下:

$$ [2:2,3:3,4:2^2,5:5,6:2\times3,7:7,8:2^3,9:3^2,10:2\times5] $$

要想找到一个最小的整除上面所有数的数,我们可以从十以内的所有质数开始寻找,首先看第一个质数二,上面列表中二的最大指数是三,也就是八的质因数分解结果,如果一个数能够被八也就是二的三次方整除,那它必然可以被二和四整除,也就是二的二次方和一次方整除。再来看三,表中三的最大指数是二,那么可以被三的平方整除的数必然可以被三整除。下一个素数是五,表中五的最大指数是一,所以这个数应该整除五。最后一个素数是七,最大指数也是一,所以这个数也应该被七整除。综上,整除表中所有数的最小数应该就是所有数的质因数分解中,各个素数的最高次幂相乘的结果,也就是\(2^3\times3^2\times5\times7=2520\)

显然我们直接利用这个算法来求解题目中的问题,但是我们仍然可以对这个算法做进一步的改进。按照这个算法,我们需要对所有数进行质因数分解来求取各个质数的最大次幂,这个计算相当耗费时间,有没有更快的方法?因为我们只关心各个素数的最大次幂,而不关心各个数的具体质因数分解方式,显然任何素数的最大次幂是使得其不超过终点数的数,比如求一至十的最小公倍数,终点数是十,则二的最高次幂只能是三,而不能是四,因为二的四次方等于十六大于十;同理,三的最高次幂只能是二,因为三的三次方也会大于十。依次类推,五和七的指数都只能是一,因这它们的平方都超过十。在这里我们看到另一个优化技巧,也就是我们只需要求那些其平方不大于终点数的素数的最大次幂,因为那些平方大于终点数的素数,其指数必然是一。最后,根据上面的推理,要求素数的最高次幂,只需要求以该素数为底,以终点数为真数的对数并下取整即可,即有:

$$ p_i^e\le N \Rightarrow e=\lfloor ln(N)/ln(p_i)\rfloor $$

对于题目中的问题规模,第二种算法相对于第二种算法的优势并不明显。在我的电脑上,第一种算法耗时5.5微秒,第二种算法耗时33.6微秒;但当\(N=1000\)时,第一种算法耗时938微秒,第二种算法耗时618微秒,第二种算法时间已经更短。进一步增加问题规模,当\(N=10^4\)时,第一种算法耗时63.5毫秒,第二种算法耗时7.22毫秒;当\(N=10^5\)时,第一种算法耗时5.85秒,第二种算法耗时198毫秒,两者的效率差距已经差别很大。总体而言,第一种算法的时间复杂度接近\(O(n^2)\),第二种算法的时间复杂度接近\(O(nlogn)\)。两种算法的实现代码如下:

# approach 1, time complexity = O(n^2)

from math import gcd
from functools import reduce

def lcm(n):
    def lcm(a, b):
        return (a * b) // gcd(a, b)
    return reduce(lcm, range(1,n+1))

# approach 2, time complexity = O(nlog(n))

from sympy import primerange
from math import sqrt,log,floor

def main(n=20):
    primes = list(primerange(1,n))
    i,ans = 0,1
    while primes[i] < sqrt(n):
        e = floor(log(n)/log(primes[i]))
        ans *= (primes[i])**e
        i += 1
    for p in primes[i:]:
        ans *= p
    return ans