打印numb除数乘积的高效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

您可以通过只循环到小于平方根的方式消除循环中的if语句，并检查循环外部的平方根整数。

你提出的这个问题很奇怪。我很难想象它的用途，除了它可能是一门课程的作业。我的第一个想法是预先计算一个素数列表，然后只对这些素数进行测试，但我想你是在刻意计算非素数因子？一、 如果这个数字有2和3，你也算6。

如果你使用一个预先计算好的素数表，那么你就必须在结果中包含所有可能的素数组合，这会变得更加复杂。

对于这类问题，C语言确实是一种很好的语言，因为即使是次优算法也运行得非常快。在

Answer 2

你需要澄清你所说的“除数乘积”是什么意思。问题中发布的代码还不适用于任何定义。这听起来像是家庭作业问题。如果是这样，那么也许你的导师希望你跳出代码去思考，以达到时间目标。在

如果你的意思是唯一素数的乘积，例如72给出2*3=6，那么有一个素数列表就是正确的方法。只需运行列表直到数字的平方根，将当前素数乘以结果。没有那么多，所以你甚至可以把它们硬编码到你的程序中。在

如果你指的是所有除数的乘积，不管是素数还是非素数，那么想想除数是什么是很有帮助的。与其他答案和你的答案中建议的暴力方法相比，你可以获得严重的速度增益。我想这是你的老师想要的。在

如果除数是在列表中排序的，那么它们成对出现，相乘到n1和n，2和n/2，等等，除了n是一个完全平方的情况，其中平方根是一个不与任何其他除数配对的除数。在

所以结果是n除以除数的一半的幂（不管n是否是平方）。在

要计算这个值，请使用素数列表找到素数因式分解。也就是说，求2除以n的幂，然后求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=139314069504。在

通过数学运算，该算法可以变得比O（n）算法好得多。但由于输入中n的大小相对较小，因此很难提前估计速度增益。在

Answer 3

好吧，我认为这接近最佳算法。它为范围内的每个数（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语言可以加快速度在