通过计算 素数分解, 可以找到一个数字的所有除数。每个除数必须是因式分解中素数的组合。
如果有素数列表,这是获得因式分解的简单方法:
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
这称为审判分庭。有很多更有效的方法可以做到这一点。请参阅此处以获取概述。
现在,计算除数非常简单:
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
计算所有除数的效率取决于查找素数的算法(此处小概述)以及因式分解算法。对于大量用户,后者总是很慢,对此您无能为力。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)