高效的Python代码，用于打印一个数字的因数积。

Question

我正在尝试解决一个涉及打印给定数字所有约数的乘积的问题。测试用例的数量是1 <= t <= 300000，数字本身可以在1 <= n <= 500000范围内。

我编写了以下代码，但它总是超过2秒的时间限制。有没有办法加快代码速度？

from math import sqrt

def divisorsProduct(n):
    ProductOfDivisors=1

    for i in range(2,int(round(sqrt(n)))+1):
        if n%i==0: 
            ProductOfDivisors*=i

            if n/i != i:
                ProductOfDivisors*=(n/i)    

    if ProductOfDivisors <= 9999:
        print ProductOfDivisors
    else:
        result = str(ProductOfDivisors)
        print result[len(result)-4:] 

T = int(raw_input())

for i in range(1,T+1):
    num = int(raw_input())
    divisorsProduct(num)

谢谢。

- jim

---

重复？https://dev59.com/5HVC5IYBdhLWcg3w1Exq - Johan Kotlinski

Answer 1

你需要澄清“除数积”是什么意思。问题中发布的代码对于任何定义都不起作用。这似乎是一个家庭作业问题。如果是这样，那么也许你的教练希望你走出代码以满足时间目标。

如果你的意思是唯一质因子积，例如72给出2*3 = 6，则拥有质数列表是正确的方法。只需在列表中运行到数字的平方根，将现有质数乘入结果即可。数量并不多，所以您甚至可以将它们硬编码到程序中。

如果您的意思是所有除数（质数或非质数）的积，则有助于考虑除数是什么。您可以比其他答案和您的粗略力量方法取得严重的速度增益。我怀疑这就是您的教练的意图。

如果除数按列表排序，则它们会成对出现，相乘为n-1和n，2和n/2等 -- 除了n是完全平方数的情况，其中平方根是不与任何其他人配对的除数。

因此，结果将是除数数量的一半的n的幂次（无论n是否为平方数）。

要计算这个值，请使用您的质数列表找到质因数分解。也就是说，找到除n外的所有2的幂，然后是3的幂，等等。为此，请取出所有2、然后是3等。

你正在取因数的数字将变得更小，所以你可以对较小的中间数字进行平方根测试，以查看是否需要继续向上查找质数列表。为了提高一些速度，测试p*p <= m，而不是p <= sqrt(m)

一旦您有了质因数分解，就很容易找到除数的数量。例如，假设分解是2^i * 3^j * 7^k。然后，由于每个除数使用相同的质因数，并且指数小于或等于n中的那些，包括0的可能性，则除数的数量为（i+1）（j+1）（k+1）。

例如，72 = 2^3 * 3^2，因此除数的数量为4*3 = 12，它们的乘积为72^6 = 139,314,069,504。

通过使用数学，算法可以比O(n)更好。但是由于输入中的n相对较小，因此很难预先估计速度增益。

- user66363

---

我本来想添加注释，但我认为你已经很好地处理了所有重要的数学细节。另请参阅http://en.wikipedia.org/wiki/Divisor_function。 - Jason S

Answer 2

好的，我认为这已经接近最优算法了。它可以为range(500000)中的每个数字生成其因数乘积。

import math

def number_of_divisors(maxval=500001):
    """ Example: the number of divisors of 12 is 6:  1, 2, 3, 4, 6, 12.
        Given a prime factoring of n, the number of divisors of n is the
        product of each factor's multiplicity plus one (mpo in my variables).

        This function works like the Sieve of Eratosthenes, but marks each
        composite n with the multiplicity (plus one) of each prime factor. """
    numdivs = [1] * maxval   # multiplicative identity
    currmpo = [0] * maxval

    # standard logic for 2 < p < sqrt(maxval)
    for p in range(2, int(math.sqrt(maxval))):
        if numdivs[p] == 1:   # if p is prime
            for exp in range(2,50): # assume maxval < 2^50
                pexp = p ** exp
                if pexp > maxval:
                    break
                exppo = exp + 1
                for comp in range(pexp, maxval, pexp):
                    currmpo[comp] = exppo
            for comp in range(p, maxval, p):
                thismpo = currmpo[comp] or 2
                numdivs[comp] *= thismpo
                currmpo[comp] = 0  # reset currmpo array in place

    # abbreviated logic for p > sqrt(maxval)
    for p in range(int(math.sqrt(maxval)), maxval):
        if numdivs[p] == 1:   # if p is prime
            for comp in range(p, maxval, p):
                numdivs[comp] *= 2

    return numdivs

# this initialization times at 7s on my machine
NUMDIV = number_of_divisors()

def product_of_divisors(n):
    if NUMDIV[n] % 2 == 0:
        # each pair of divisors has product equal to n, for example
        # 1*12 * 2*6 * 3*4  =  12**3
        return n ** (NUMDIV[n] / 2)
    else:
        # perfect squares have their square root as an unmatched divisor
        return n ** (NUMDIV[n] / 2) * int(math.sqrt(n))

# this loop times at 13s on my machine
for n in range(500000):
    a = product_of_divisors(n)

在我的非常慢的电脑上，计算每个数字的因数数量需要7秒钟，然后计算每个数字的因数乘积需要13秒钟。当然，将其转换成C语言可以加速运算。（@那些有快速电脑的人：在你们的电脑上要多久？）

- krubo

---

我的机器在2.565秒的实际时间（2.479秒的用户时间）内运行了你的代码。我还没有尝试分别计时各个部分。 - Will Harris

Answer 3

你可以通过只循环到小于平方根的方式来消除循环中的if语句，并在循环外检查平方根是否为整数。

你提出的问题相当奇怪。我很难想象它有什么用处，除了可能是课程作业之外。我的第一个想法是预先计算质数列表，并仅针对这些进行测试，但我假设你故意计算非质数因子？也就是说，如果这个数字有2和3的因子，你也会计算6。

如果你使用预先计算的质数表，那么你还必须随后包括所有可能的质数组合在你的结果中，这变得更加复杂。

C语言真的是这种事情的绝佳语言，因为即使是次优算法也能运行得非常快。

- Matthias Wandel

---

相反地，对于这种类型的任务来说，C语言真的很糟糕，因为人们通常可以通过蛮力法而无需考虑如何设计良好的算法。 - Johan Kotlinski

@Matthias：预计算质数并仅测试它们是合理的。一旦他有了他的数字的质因数分解，计算非质数除数就很简单了。 - Brian