divisor function 是自然数的除数之和。

做了一点研究,我发现 this 是一个非常好的方法,如果你想找到给定自然数 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

最佳答案

在计算除数之和时,您需要以 p1k1 p2k2 ... 的形式对 n 进行因式分解——也就是说,您需要因式分解中每个素数的指数。目前,您通过计算素因数的平面列表,然后调用 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

上面代码的注意事项:
  • 我已经转换了这段代码,以便它生成分解,而不是构造一个列表(通过重复调用 append )并返回它。在 Python 中,这种转换几乎总是一种改进,因为它允许您在元素生成时一个一个地使用它们,而不必将整个序列存储在内存中。
  • 这是 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)
    

    关于python - 你将如何实现除数函数?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14359936/

    10-11 16:59