得到一个数字的所有因数最好的办法是什么？

这是非常愚蠢的方式：

def divisorGenerator(n): for i in xrange(1,n/2+1): if n%i == 0: yield i yield n 

我想得到的结果是类似于这个，但我想要一个更聪明的algorithm（这一个是太慢，愚蠢的:-)

我可以快速find主要因素和多样性。 我有一个生成器，以这种方式生成的因素：

（factor1，multiplicity1）
（因子2，重数2）
（factor3，multiplicity3）
等等…

即输出

 for i in factorGenerator(100): print i 

是：

 (2, 2) (5, 2) 

我不知道这对于我想要做的事有多大用处（我把它编码为其他问题），无论如何，我想要一个更聪明的方法

 for i in divisorGen(100): print i 

输出这个：

 1 2 4 5 10 20 25 50 100 

---

更新：非常感谢格雷格Hewgill和他的“聪明的方式”:)计算1亿的所有因数花了0.01s与他的方式反对39愚蠢的方式在我的机器上，非常酷：D

更新2：停止说这是这个职位的重复。 计算给定数字的除数不需要计算所有除数。 这是一个不同的问题，如果你认为它不是那么在维基百科上寻找“除数函数”。 在发帖前阅读问题和答案，如果你不明白这个话题是什么，只是不加，没有用处，已经给出了答案。

Answer 1

鉴于你的factorGenerator函数，这里是一个应该工作的divisorGen：

 def divisorGen(n): factors = list(factorGenerator(n)) nfactors = len(factors) f = [0] * nfactors while True: yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1) i = 0 while True: f[i] += 1 if f[i] <= factors[i][1]: break f[i] = 0 i += 1 if i >= nfactors: return 

这个algorithm的整体效率将完全取决于factorGenerator的效率。

Answer 2

为了扩大Shimi所说的话，你只应该运行从1到n的平方根的循环。 然后find这对，做n / i ，这将覆盖整个问题的空间。

还有人指出，这是一个NP，或“困难”的问题。 彻底search，你这样做的方式，大约是一样好，以获得有保证的答案。 这个事实被encryptionalgorithm等用来帮助保护它们。 如果有人解决这个问题，我们目前的“安全”通信大多数（如果不是全部的话）将会变得不安全。

Python代码：

 import math def divisorGenerator(n): large_divisors = [] for i in xrange(1, int(math.sqrt(n) + 1)): if n % i == 0: yield i if i*i != n: large_divisors.append(n / i) for divisor in reversed(large_divisors): yield divisor print list(divisorGenerator(100)) 

哪个应该输出一个列表，如：

 [1，2，4，5，10，20，25，50，100]

Answer 3

虽然已经有很多解决scheme，我真的不得不发布这:)

这一个是：

• 可读
• 短
• 自包含，复制和粘贴就绪
• 快速（在有很多主要因素和因数的情况下，比Greg的解决scheme快10倍以上）
• python3，python2和pypy兼容

码：

 def divisors(n): # get factors and their counts factors = {} nn = n i = 2 while i*i <= nn: while nn % i == 0: if not i in factors: factors[i] = 0 factors[i] += 1 nn //= i i += 1 if nn > 1: factors[nn] = 1 primes = list(factors.keys()) # generates factors from primes[k:] subset def generate(k): if k == len(primes): yield 1 else: rest = generate(k+1) prime = primes[k] for factor in rest: prime_to_i = 1 # prime_to_i iterates prime**i values, i being all possible exponents for _ in range(factors[prime] + 1): yield factor * prime_to_i prime_to_i *= prime # in python3, `yield from generate(0)` would also work for factor in generate(0): yield factor 

Answer 4

我喜欢格雷格的解决scheme，但我希望它更像Python。 我觉得它会更快，更可读; 所以经过一段时间的编码之后我就出来了。

前两个函数需要做列表的笛卡尔积。 只要出现这个问题，就可以重复使用。 顺便说一下，我必须自己编程，如果有人知道这个问题的标准解决scheme，请随时与我联系。

“Factorgenerator”现在返回一个字典。 然后字典被送入“除数”，用它来首先生成一个列表列表，其中每个列表是以p素数forms的因子列表。 然后我们做出这些列表的笛卡尔积，最后我们用Greg的解法来生成除数。 我们对它们进行分类，然后归还。

我testing了它，它似乎比以前的版本快一点。 我testing了它作为一个更大的程序的一部分，所以我不能说真的有多快。

Pietro Speroni（pietrosperoni点它）

 from math import sqrt ############################################################## ### cartesian product of lists ################################## ############################################################## def appendEs2Sequences(sequences,es): result=[] if not sequences: for e in es: result.append([e]) else: for e in es: result+=[seq+[e] for seq in sequences] return result def cartesianproduct(lists): """ given a list of lists, returns all the possible combinations taking one element from each list The list does not have to be of equal length """ return reduce(appendEs2Sequences,lists,[]) ############################################################## ### prime factors of a natural ################################## ############################################################## def primefactors(n): '''lists prime factors, from greatest to smallest''' i = 2 while i<=sqrt(n): if n%i==0: l = primefactors(n/i) l.append(i) return l i+=1 return [n] # n is prime ############################################################## ### factorization of a natural ################################## ############################################################## def factorGenerator(n): p = primefactors(n) factors={} for p1 in p: try: factors[p1]+=1 except KeyError: factors[p1]=1 return factors def divisors(n): factors = factorGenerator(n) divisors=[] listexponents=[map(lambda x:k**x,range(0,factors[k]+1)) for k in factors.keys()] listfactors=cartesianproduct(listexponents) for f in listfactors: divisors.append(reduce(lambda x, y: x*y, f, 1)) divisors.sort() return divisors print divisors(60668796879) 

PS这是我第一次张贴到计算器。 我期待着任何反馈。

Answer 5

我想你可以停在math.sqrt(n)而不是n / 2。

我会给你例子，以便你可以很容易地理解。 现在sqrt(28)是5.29所以ceil(5.29)将是6.所以我如果我将停在6那么我可以得到所有的因数。 怎么样？

首先看代码，然后看图像：

 import math def divisors(n): divs = [1] for i in xrange(2,int(math.sqrt(n))+1): if n%i == 0: divs.extend([i,n/i]) divs.extend([n]) return list(set(divs)) 

现在，看到下面的图像：

可以说，我已经添加了1到我的除数列表，我以i=2开头

因此，在所有迭代结束时，我已经将商和除数添加到我的列表中，所有28的除数都被填充。

希望这可以帮助。 如果您有任何疑问，请不要犹豫，我会很乐意帮助您:)。

来源： 如何确定一个数字的除数
圆的半径 – 代码和图像

Answer 6

改编自CodeReview ，这是一个变种，它适用于num=1 ！

 from itertools import product import operator def prod(ls): return reduce(operator.mul, ls, 1) def powered(factors, powers): return prod(f**p for (f,p) in zip(factors, powers)) def divisors(num) : pf = dict(prime_factors(num)) primes = pf.keys() #For each prime, possible exponents exponents = [range(i+1) for i in pf.values()] return (powered(primes,es) for es in product(*exponents)) 

Answer 7

假设factors函数返回n的因子（例如， factors(60)返回列表[2，2，3，5]），下面是一个计算n的因子的函数 ：

 function divisors(n) divs := [1] for fact in factors(n) temp := [] for div in divs if fact * div not in divs append fact * div to temp divs := divs + temp return divs 

Answer 8

这是我的解决scheme。 这似乎是愚蠢的，但效果很好…我试图find所有适当的除数，所以循环从i = 2开始。

 import math as m def findfac(n): faclist = [1] for i in range(2, int(m.sqrt(n) + 2)): if n%i == 0: if i not in faclist: faclist.append(i) if n/i not in faclist: faclist.append(n/i) return facts 

Answer 9

老问题，但这里是我的意见：

 def divs(n, m): if m == 1: return [1] if n % m == 0: return [m] + divs(n, m - 1) return divs(n, m - 1) 

你可以用以下方式

 def divisorGenerator(n): for x in reversed(divs(n, n)): yield x 

注：对于支持的语言，这可能是尾recursion。

Answer 10

这是一个聪明而又快速的方法，可以在纯Python 3.6中使用10 ** 16以上的数字，

 from itertools import compress def primes(n): """ Returns a list of primes < n for n > 2 """ sieve = bytearray([True]) * (n//2) for i in range(3,int(n**0.5)+1,2): if sieve[i//2]: sieve[i*i//2::i] = bytearray((ni*i-1)//(2*i)+1) return [2,*compress(range(3,n,2), sieve[1:])] def factorization(n): """ Returns a list of the prime factorization of n """ pf = [] for p in primeslist: if p*p > n : break count = 0 while not n % p: n //= p count += 1 if count > 0: pf.append((p, count)) if n > 1: pf.append((n, 1)) return pf def divisors(n): """ Returns an unsorted list of the divisors of n """ divs = [1] for p, e in factorization(n): divs += [x*p**k for k in range(1,e+1) for x in divs] return divs n = 600851475143 primeslist = primes(int(n**0.5)+1) print(divisors(n)) 

Answer 11

 return [x for x in range(n+1) if n/x==int(n/x)] 

Answer 12

对我来说，这工作正常，也是干净的（Python 3）

 def divisors(number): n = 1 while(n<number): if(number%n==0): print(n) else: pass n += 1 print(number) 

不是很快，但如果你想要一行一行地返回除数，如果你真的想要，也可以做list.append（n）和list.append（number）