<p>好吧,我认为这接近最佳算法。它为范围内的每个数(500000)生成_除数的乘积。在</p>
<pre><code>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)
</code></pre>
<p>在我的速度很慢的机器上,计算每个数的除数需要7秒,然后计算每个数的除数乘积需要13秒。当然,把它翻译成C语言可以加快速度在</p>