【每天进步一点点】Python解题笔记（05篇）

jerryxjr1220

今天继续来解“欧拉计划”的第5题：求能被1~20以内任意一个数整除的最小的正整数。

其实，稍微有点数学基础的应该马上就能反应过来，这题就是要求1~20以内所有数的最小公倍数。

那么最小公倍数怎么求？

1. 直接用现成模块，还记得algorithms的模块吗？里面有非常多实用的数学公式可以直接调用，包括最小公倍数函数lcm

from algorithms.math.lcm import lcm

2. 如果没有这个模块也不要紧，我们就自己计算吧，也不复杂。
最小公倍数=两数的乘积除以最大公约数，而最大公约数的函数是在math模块中自带的。

def lcm(a,b):
        from math import gcd
        return a*b//gcd(a,b)

有了最小公倍数函数接下来就简单了，只需要依次按1~20把每个数和前一个数计算的结果进行最小公倍数计算就可以了。

这里介绍一个很有用的函数reduce。（从python 3.1开始，reduce函数被放在了functools模块中）

reduce()函数接收的参数一个函数 f，一个list，reduce()传入的函数 f 必须接收两个参数，reduce()对list的每个元素反复调用函数f，并返回最终结果值。

在本题中，我们可以这样，就能得出最终的结果了。

from functools import reduce
print(reduce(lcm, range(1,21)))

下面，我们再来看一下另一种解题方法。虽然效率并不如第一种方法快，不过也不失为一种新的解题思路。

我们可以用字典把20以下所有的数进行因式分解，然后把所有因子进行统计，其乘积就是要求的值。

因式分解的方法，在小甲鱼的视频教程中已经有了，我就不再重复了。我在这里调用collections模块的Counter模块对分解完的因子进行统计。

Counter类的目的是用来跟踪值出现的次数。它是一个无序的容器类型，以字典的键值对形式存储，其中元素作为key，其计数作为value。计数值可以是任意的Interger（包括0和负数）。Counter类和其他语言的bags或multisets很相似。

from collections import Counter
def fenjie(n):
        primes = [2,3,5,7,11,13,17,19]
        yinzi = []
        while n not in primes:
                for i in primes:
                        if n % i == 0:
                                yinzi.append(i)
                                n //= i
                                break
        else:
                yinzi.append(n)
        return Counter(yinzi)

然后，我们就从这个统计好的字典中依次提取出每个因子以及出现频次，放入到大字典中。

dic = {}
for i in range(2, 21):
        for yz, num in fenjie(i).items():
                dic[yz] = max(dic.get(yz, 0), num)

最后一步，就是对大字典中的所有因子进行累乘（因子的出现次数作为次方数）。

total = 1
for k,v in dic.items():
        total *= k**v
print(total)

最终就能得到我们需要的值。

同一道题从不同的角度去思考，就能有不同的解题方法，你学会了吗？