3

除数函数是一个自然数的除数之和。

做了一点研究，我发现如果你想找到给定自然数 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元素的列表，但我没有使用其中的大部分）。

您将如何改进/实施它？

PS这是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
4

5 回答 5

8

在计算除数之和时，您需要以p 1 k 1 p 2 k 2 ...的形式对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

上面代码的注释：

  1. 我已经转换了这段代码，以便它生成分解，而不是构造一个列表（通过重复调用append）并返回它。在 Python 中，这种转换几乎总是一种改进，因为它允许您在生成元素时一个一个地使用它们，而不必将整个序列存储在内存中。

  2. 这是doctest可以很好地工作的那种功能。

现在计算除数的总和非常简单：不需要存储检查的因子集或计算每个因子出现的次数。实际上，您只需一行即可完成：

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)
于 2013-01-16T14:50:23.877 回答
1 
def sum_divisors(n):
    assert n > 0
    if n == 1:
        return 0
    sum = 1
    if n % 2 == 0:              # if n is even there is a need to go over even numbers
        i = 2
        while i < sqrt (n):
            if n % i == 0:
                sum = sum + i + (n//i)  # if i|n then n/i is an integer so we want to add it as well
            i = i + 1
        if type (sqrt (n)) == int:  # if sqrt(n)|n we would like to avoid adding it twice
            sum = sum + sqrt (n)
    else:
        i = 3
        while i < sqrt (n):     # this loop will only go over odd numbers since 2 is not a factor
            if n % i == 0:
                sum = sum + i + (n//i)  # if i|n then n/i is an integer so we want to add it as well
            i = i + 2
        if type (sqrt (n)) == int:  # if sqrt(n)|n we would like to avoid adding it twice
            sum = sum + sqrt (n)
    return sum
于 2014-11-13T12:54:40.667 回答
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
于 2013-01-16T13:58:16.260 回答
1

为什么使用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
于 2013-01-17T08:12:47.677 回答
0

这是我在我的 Java 数字实用程序（广泛用于 Project Euler）中所做的：

  • 使用显式指数生成素数分解（请参阅 Gareth Rees 的答案）。

  • 基于它展开各种函数中的素数分解。即，使用与素数分解相同的算法，但直接计算期望值而不是存储因子和指数。

  • 默认情况下，测试只除以二和奇数。我有方法firstDivisor(n)和nextDivisor(n,d)为此。

  • 可以选择为所有低于界限的数字预先计算一个最小除数表。如果您需要分解所有或大多数低于界限的数字（将速度提高约sqrt(limit)），这将非常有用。我将表连接到firstDivisor(n)andnextDivisor(n,d)方法中，所以这不会改变分解算法。

于 2013-01-18T08:20:21.150 回答