高效的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)

谢谢.

Answer 1

你需要通过"除数的产物"来表达你的意思.问题中发布的代码对任何定义都不起作用.这听起来像是一个家庭作业问题.如果是,那么也许你的导师希望你在代码之外思考以达到时间目标.

如果你的意思是唯一素数除数的乘积,例如,72给出2*3 = 6,那么有一个素数列表是要走的路.只需遍历列表,直到数字的平方根,将当前的素数乘以结果.没有那么多,所以你甚至可以将它们硬编码到你的程序中.

如果你的意思是所有除数的产物,无论是否为素数,那么考虑除数是什么是有帮助的.您可以通过其他答案和您的答案中建议的强力方法获得严重的速度提升.我怀疑这是你教练的意图.

如果除数按列表排序,则它们成对出现,乘以n - 1和n,2和n/2等 - 除了n是一个完美的正方形,其中平方根是与任何其他人不配对的除数.

因此,结果将是除数的一半的幂的幂(无论n是否是正方形).

要计算此数,请使用素数列表查找素数因子分解.也就是说,找到2除以n的幂,然后求3的幂,等等.为此,取出所有的2s,然后是3s等.

从中获取因子的数量将变小,因此您可以对较小的中间数进行平方根测试,以查看是否需要继续填充素数列表.为了获得一些速度,测试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的尺寸相对较小,因此很难提前估算速度增益.