By

文章目錄

两年前面试4399时，和面试官说起用Python来做欧拉工程，于是面试官很感兴趣地说，有没有写一些小模块来求解，当时只是摇头，想想写写算法题还可以，写模块就太大了。现在想来，模块也无非是一些函数的集合，在接欧拉工程的过程中，就会经常遇到一些问题，需要用类似的方法解决，如果把这些共同的部分写在一起，不也是一个模块了？

质因子分解是经常需要用到的，这里给一个解决的办法。例如要求120的质因子分解，先用2去除，一直到不能整除为止，记得到2^3,以及剩下的15，之后用3去除，得到3以及剩下的5，之后用5去除，得到5以及0，分解过程结束。写成程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import defaultdict
def get_divisors(n):
    divisors = defaultdict(int)
    if n % 2 == 0:
        while n % 2 == 0:
            divisors[2] += 1
            n /= 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                divisors[i] += 1
                n /= i
        i += 2
    if n > 1:
        divisors[n] += 1
    return divisors

有了这个方法就可以用来求一些数的最小公倍数，例如求，2 3 5 8 的最小公倍数

1
2
3
4
5
6
7
8
9
10
L = [2, 3, 5, 8]
factors = defaultdict(int)
for i in L:
    divisors = get_divisors(i)
    for d in divisors.iterkeys():
        factors[d] = max(factors[d], divisors[d])
res = 1
for d in factors.iterkeys():
    res *= d ** factors[d]
print res

打赏作者

文章目錄