如何实现一个除数函数？

Question

除数函数就是一个自然数的所有除数加起来的总和。

我做了一些研究，发现这个方法非常好，如果你想找一个给定自然数N的除数函数，所以我尝试用Python来写代码：

def divisor_function(n):
    "Returns the sum of divisors of n"
    checked = [False]*100000
    factors = prime_factors(n)
    sum_of_divisors = 1 # It's = 1 because it will be the result of a product
    for x in factors:
        if checked[x]:
            continue
        else:
            count = factors.count(x)
            tmp = (x**(count+1)-1)//(x-1)
            sum_of_divisors*=tmp
            checked[x]=True
    return sum_of_divisors

这个代码运行得不错，但我觉得可以改进一下（比如：我创建了一个有100000个元素的列表，但大部分元素我并没有用到）。

你会怎么改进或实现它呢？

附注：这是prime_factors的代码：

def prime_factors(n):
    "Returns all the prime factors of a positive integer"
    factors = []
    d = 2
    while (n > 1):
        while (n%d==0):
            factors.append(d)
            n /= d
        d = d + 1
        if (d*d>n):
            if (n>1): factors.append(int(n));
            break;
    return factors

Answer 1

你只需要改动两行代码：

def divisor_function(n):
    "Returns the sum of divisors of n"
    checked = {}
    factors = prime_factors(n)
    sum_of_divisors = 1 # It's = 1 because it will be the result of a product
    for x in factors:
        if checked.get(x,False):
            continue
        else:
            count = factors.count(x)
            tmp = (x**(count+1)-1)//(x-1)
            sum_of_divisors*=tmp
            checked[x]=True
    return sum_of_divisors

Answer 2

为什么要使用 dict 或 set，或者 count() 呢，既然 prime_factors() 保证会按升序返回因子？你只需要处理一个 之前 的因子。计数其实可以在循环中完成：

def divisor_function(n):
    "Returns the sum of divisors of n"
    factors = prime_factors(n)
    sum_of_divisors = 1 
    count = 0; prev = 0;
    for x in factors:
        if x==prev:
            count += 1
        else:
            if prev: sum_of_divisors *= (prev**(count+1)-1)//(prev-1)
            count = 1; prev = x;
    if prev: sum_of_divisors *= (prev**(count+1)-1)//(prev-1)
    return sum_of_divisors

Answer 3

在计算一个数的所有因子的和时，你需要把这个数 n 分解成质因数的形式，比如 p₁^k₁ p₂^k₂ 等等，也就是说你需要知道每个质数在分解中出现的次数。现在你是通过先计算出一个质因数的列表，然后再用 count 来算出每个质数的次数，这样做其实很浪费时间，因为你可以直接生成你需要的质因数分解格式，像这样：

def factorization(n):
    """
    Generate the prime factorization of n in the form of pairs (p, k)
    where the prime p appears k times in the factorization.

    >>> list(factorization(1))
    []
    >>> list(factorization(24))
    [(2, 3), (3, 1)]
    >>> list(factorization(1001))
    [(7, 1), (11, 1), (13, 1)]
    """
    p = 1
    while p * p < n:
        p += 1
        k = 0
        while n % p == 0:
            k += 1
            n //= p
        if k:
            yield p, k
    if n != 1:
        yield n, 1

关于上面代码的几点说明：

1. 我把这个代码改成了直接 生成 分解结果，而不是先构建一个列表（通过多次调用 append），然后再返回。对于 Python 来说，这种改动几乎总是有好处，因为这样你可以在生成每个元素的时候就使用它，而不需要把整个序列都存储在内存里。

2. 这种函数特别适合用 doctests 来测试。

现在计算因子的和就简单多了：你不需要存储已经检查过的因子集合，也不需要统计每个因子出现的次数。实际上，你只需要一行代码就能完成：

from operator import mul

def sum_of_divisors(n):
    """
    Return the sum of divisors of n.

    >>> sum_of_divisors(1)
    1
    >>> sum_of_divisors(33550336) // 2
    33550336
    """
    return reduce(mul, ((p**(k+1)-1) // (p-1) for p, k in factorization(n)), 1)