擅长:python、mysql、java
<p>你需要澄清你所说的“除数乘积”是什么意思。问题中发布的代码还不适用于任何定义。这听起来像是家庭作业问题。如果是这样,那么也许你的导师希望你跳出代码去思考,以达到时间目标。在</p>
<p>如果你的意思是唯一素数的乘积,例如72给出2*3=6,那么有一个素数列表就是正确的方法。只需运行列表直到数字的平方根,将当前素数乘以结果。没有那么多,所以你甚至可以把它们硬编码到你的程序中。在</p>
<p>如果你指的是所有除数的乘积,不管是素数还是非素数,那么想想除数是什么是很有帮助的。与其他答案和你的答案中建议的暴力方法相比,你可以获得严重的速度增益。我想这是你的老师想要的。在</p>
<p>如果除数是在列表中排序的,那么它们成对出现,相乘到n1和n,2和n/2,等等,除了n是一个完全平方的情况,其中平方根是一个不与任何其他除数配对的除数。在</p>
<p>所以结果是n除以除数的一半的幂(不管n是否是平方)。在</p>
<p>要计算这个值,请使用素数列表找到素数因式分解。也就是说,求2除以n的幂,然后求3的幂,等等。要这样做,去掉所有的2,然后3,等等</p>
<p>你去掉因子的数字会变小,所以你可以对较小的中间数做平方根检验,看看你是否需要继续向上排列素数。为了获得一些速度,测试p*p<;=m,而不是p<;=sqrt(m)</p>
<p>一旦有了素数因式分解,就很容易找到除数的个数。例如,假设因式分解是2^i*3^j*7^k。那么,由于每个除数使用相同的素数因子,且指数小于或等于n中的指数(包括0的可能性),那么除数的数目是(i+1)(j+1)(k+1)。在</p>
<p>例如,72=2^3*3^2,所以除数是4*3=12,它们的乘积是72^6=139314069504。在</p>
<p>通过数学运算,该算法可以变得比O(n)算法好得多。但由于输入中n的大小相对较小,因此很难提前估计速度增益。在</p>