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

好的，我觉得这个算法差不多是最优的了。它可以计算出范围在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语言的话，可以加快速度。（@某个有快电脑的人：你们的机器上需要多长时间？）

Answer 3

你需要先弄清楚“因子的乘积”是什么意思。问题中提供的代码目前还没有适用于任何定义。这听起来像是个作业题。如果真是这样，可能你的老师希望你能跳出代码的框架，去思考如何在时间上达到目标。

如果你指的是独特的质因子的乘积，比如72的质因子是2和3，那么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相对较小，事先很难估计你能提高多少速度。