0

通常我使用以下代码来查找除数的数量，直到给定的 n（tau 函数）：

L=[0 for i in range(N+1)]
for i in range(1,N+1):
    for j in range(i, N+1,i):
        L[j]+=1
print L

哪个输出

[0, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4]

但是如果我想输出 n^2 的除数呢？现在它正在查看 n=0,1,2,3,4,5,6,7,8,9,10，但我想更改它，所以它实际上正在查看 0,1,4,9,16， 25,36,49,64,81,100（无需与任何其他数字混淆）。

输出应如下所示：

[0, 1, 3, 3, 5, 3, 9, 3, 7, 5, 9]
4

3 回答 3

2

根据有多大n，Nolen 的答案可能就足够了（公平地说，您的原始代码一开始就没有优化）。然而，值得注意的是什么n**2 是. 如果我们可以分解一个数字，比如说10，我们会得到：

10    = (2**1)*(5**1)
10**2 = (2**(1+1))*(5**(1+1)) = (2**2)*(5**2)

即素数分解中的指数中的数字只是翻了一番。假设您已经可以找到一个数字的素数分解n（您的代码可以修改），除数的数量可以n**2通过（伪代码）找到

div  := (list of divisors of n)
div2 := (a list with two copies of div)
loop through all combinations div2:
      if combo <= sqrt(n): keep unique

如果我们这样做，10我们会得到：

div  := (1,2,5,10)
div2 := (1,2,5,10,1,2,5,10)
keep := (1,2,5,10,2*2,2*5) 
unique_keep := (1,2,4,5,10)

因此，每个数字都unique_keep分为10**2=100相应的因子，除了 10 的奇异情况是它自己的因子。这给出了九个除数：

1 -> 100
2 -> 50
4 -> 25
5 -> 20
10 -> 10
于 2012-04-16T14:29:46.020 回答
0

我相信你想要这样的东西？

>>> [sum(i**2 % j == 0 for j in range(1, i**2 + 1)) for i in range(11)]
[0, 1, 3, 3, 5, 3, 9, 3, 7, 5, 9]

或更一般地说

>>> def divisors(start, end, trans=lambda x:x):
...     return [sum(i % j == 0 for j in range(1, i + 1)) for i in (trans(t) for t in range(start, end+1))]
... 
>>> divisors(0, 10, lambda x: x**2)
[0, 1, 3, 3, 5, 3, 9, 3, 7, 5, 9]
>>> divisors(0, 10)
[0, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4]
于 2012-04-16T14:01:07.623 回答
0

如果你有一个数的质因数，那么计算它的因数的数量就像计算它的平方（或者，实际上是任何幂）的因数一样容易。

def factor_count(N,power):
    factor_count = list()
    for n in range(N+1):
        prime = 2
        prime_factors = list()
        exponents = list()
        while n > 1:
            while (n / prime) % 1 == 0:
                if prime not in prime_factors:
                    prime_factors.append(prime)
                    exponents.append(1)
                else:
                    exponent = exponents.pop()+1
                    exponents.append(exponent)
                n /= prime
            prime += 1
        factors = 1
        for x in exponents:
            factors *= power*x+1
        factor_count.append(factors)
    print(factor_count)

另外，我会注意到我的程序与你的程序在零有多少因素方面有所不同。修改代码以解决此问题很简单，但由于除数通常是在自然数上定义的，因此完全忽略它同样容易。

为了让您了解与给出的其他答案相比的效率：

power_factors(1000,2000000000)                                        #evaluates almost instantly despite having an exponent of 2 billion
[sum(i**2 % j == 0 for j in range(1, i**2 + 1)) for i in range(1001)] #I got fed up of waiting before it managed to finish even with just an exponent of 2
于 2012-04-16T17:00:50.967 回答