擅长:python、mysql、java
<p>你可以通过计算素数分解来找到一个数的所有除数。每个除数必须是因子分解中素数的组合。</p>
<p>如果你有一个素数列表,这是一个简单的分解方法:</p>
<pre><code>def factorize(n, primes):
factors = []
for p in primes:
if p*p > n: break
i = 0
while n % p == 0:
n //= p
i+=1
if i > 0:
factors.append((p, i));
if n > 1: factors.append((n, 1))
return factors
</code></pre>
<p>这叫审判庭。有很多更有效的方法可以做到这一点。有关概述,请参见<a href="http://en.wikipedia.org/wiki/Integer_factorization">here</a>。</p>
<p>现在计算除数很容易:</p>
<pre><code>def divisors(factors):
div = [1]
for (p, r) in factors:
div = [d * p**e for d in div for e in range(r + 1)]
return div
</code></pre>
<p>计算所有因子的效率取决于寻找素数的算法(小概图<a href="http://en.wikipedia.org/wiki/Prime_sieve">here</a>)和因子分解算法。后者对于很大数量的数据总是很慢,对此你无能为力。</p>