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

jerryxjr1220

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

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

那么最小公倍数怎么求？

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

1. from algorithms.math.lcm import lcm

复制代码

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

1. def lcm(a,b):
   
2.         from math import gcd
   
3.         return a*b//gcd(a,b)

复制代码

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

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

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

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

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

复制代码

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

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

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

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

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

复制代码

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

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

复制代码

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

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

复制代码

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

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