在Python中查找数字的所有因素的最有效的方法是什么？
有人可以向我解释一个有效的方法来find在Python（2.7）中的一个数字的所有因素？
我可以创buildalgorithm来完成这项工作，但是我认为它编码不好，并且花费很长时间来执行大量的结果。
def factors(n): return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))) 这将很快返回n的所有因素。
为什么平方根是上限？
sqrt(x) * sqrt(x) = x 。 所以如果两个因素是相同的，那么它们都是平方根。 如果你把一个因素做得更大，你必须把另一个因素变小。 这意味着两者中的一个将总是小于或等于sqrt(x) ，所以您只需要search到该点即可find两个匹配因素之一。 然后你可以用x / fac1来获得x / fac1 。
reduce(list.__add__, ...)将[fac1, fac2]的小列表join到一个长列表中。
[i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0的[i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0返回一对因子，如果n除以较小者的余数为零（它也不需要检查较大的那个;它只是通过将n除以较小的那个来得到）。
在外面的set(...)摆脱重复。 我认为这只发生在完美的广场上。 对于n = 4 ，这将返回2两次，所以set摆脱其中之一。
sqrt实际上比**0.5更快，但是我会把它作为一个自包含的代码片段来保存。
@agf提供的解决scheme非常棒，但通过检查奇偶校验，可以将任意奇数的运行时间缩短约50％。 由于奇数的因素总是奇数，所以在处理奇数时没有必要检查这些因素。
我刚开始解决项目欧拉拼图自己。 在一些问题中，在两个嵌套for循环内调用一个除数检查，因此这个函数的性能是非常重要的。
结合这个事实与agf的优秀解决scheme，我已经结束了这个function：
from math import sqrt def factors(n): step = 2 if n%2 else 1 return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))
然而，在小数目（〜<100）的情况下，这种改变的额外开销可能导致function花费更长的时间。
我跑了一些testing，以检查速度。 以下是使用的代码。 为了产生不同的情节，我相应地改变了X = range(1,100,1) 。
import timeit from math import sqrt from matplotlib.pyplot import plot, legend, show def factors_1(n): step = 2 if n%2 else 1 return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0))) def factors_2(n): return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0))) X = range(1,100000,1000) Y = [] for i in X: f_1 = timeit.timeit('factors_1({})'.format(i), setup='from __main__ import factors_1', number=10000) f_2 = timeit.timeit('factors_2({})'.format(i), setup='from __main__ import factors_2', number=10000) Y.append(f_1/f_2) plot(X,Y, label='Running time with/without parity check') legend() show()
X =范围（1,100,1） 
这里没有显着的区别，但是数字越大，优势就越明显：
X =范围（1,100000,1000）（只有奇数） 
X =范围（2,100000,100）（仅偶数） 
X =范围（1,100000,1001）（交替奇偶校验） 
agf的答案真的很酷。 我想看看是否可以重写它，以避免使用reduce() 。 这就是我想到的：
import itertools flatten_iter = itertools.chain.from_iterable def factors(n): return set(flatten_iter((i, n//i) for i in range(1, int(n**0.5)+1) if n % i == 0))
我也试过一个使用棘手的生成器函数的版本：
def factors(n): return set(x for tup in ([i, n//i] for i in range(1, int(n**0.5)+1) if n % i == 0) for x in tup)
我通过计算来计算：
start = 10000000 end = start + 40000 for n in range(start, end): factors(n)
我跑了一次，让Python编译它，然后在时间（1）命令下运行它三次，并保持最佳状态。
- 减less版本：11.58秒
- itertools版本：11.49秒
- 棘手的版本：11.12秒
请注意，itertools版本正在构build一个元组，并将其传递给flatten_iter（）。 如果我更改代码来构build一个列表，它会稍微减慢：
- iterools（list）版本：11.62秒
我相信棘手的生成器函数版本是Python中最快的。 但是它的速度并不比缩小版本快很多，根据我的测量，速度大概快了4％。
agf的答案的另一种方法：
def factors(n): result = set() for i in range(1, int(n ** 0.5) + 1): div, mod = divmod(n, i) if mod == 0: result |= {i, div} return result
进一步改善afg＆eryksun的解决scheme。 下面这段代码返回所有因素的sorting列表，而不会改变运行时间的渐近复杂度：
def factors(n): l1, l2 = [], [] for i in range(1, int(n ** 0.5) + 1): q,r = n//i, n%i # Alter: divmod() fn can be used. if r == 0: l1.append(i) l2.append(q) # q's obtained are decreasing. if l1[-1] == l2[-1]: # To avoid duplication of the possible factor sqrt(n) l1.pop() l2.reverse() return l1 + l2
想法：而不是使用list.sort（）函数来得到一个给出nlog（n）复杂度的sorting列表; 在l2上使用list.reverse（）要花费O（n）复杂度要快得多。 （这就是python的做法。）在l2.reverse（）之后，l2可以被附加到l1以获得sorting的因子列表。
注意，l1包含增加的i -s。 l2包含正在减less的q -s。 这是使用上述想法背后的原因。
我已经用时间把大部分这些精彩的答案都用来比较他们的效率和我简单的function，但是我经常看到我的performance超过了这里列出的。 我想我会分享它，看看你们都在想什么。
def factors(n): results = set() for i in xrange(1, int(math.sqrt(n)) + 1): if n % i == 0: results.add(i) results.add(int(n/i)) return results
正如它写的，你将不得不导入mathtesting，但用n **。5replacemath.sqrt（n）也应该是一样的。 我不会浪费时间检查重复项，因为重复项不能在一组中存在。
一定要抓住大于sqrt(number_to_factor)的数字，例如99的3 * 3 * 11和floor sqrt(99)+1 == 10 。
import math def factor(x): if x == 0 or x == 1: return None res = [] for i in range(2,int(math.floor(math.sqrt(x)+1))): while x % i == 0: x /= i res.append(i) if x != 1: # Unusual numbers res.append(x) return res
下面是@ agf解决scheme的替代scheme，它以更为pythonic的风格实现相同的algorithm：
def factors(n): return set( factor for i in range(1, int(n**0.5) + 1) if n % i == 0 for factor in (i, n//i) )
这个解决scheme可以在Python 2和Python 3中运行，不需要导入，而且可读性更强。 我没有testing过这个方法的性能，但渐近地应该是一样的，如果性能是一个严重的问题，那么这两个解决scheme都不是最优的。
这是另一个没有减less的替代品，大量地执行。 它使用sum来压扁列表。
def factors(n): return set(sum([[i, n//i] for i in xrange(1, int(n**.5)+1) if not n%i], []))
这里是一个例子，如果你想使用质数来快得多。 这些列表很容易在互联网上find。 我在代码中添加了注释。
# http://primes.utm.edu/lists/small/10000.txt # First 10000 primes _PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, # Mising a lot of primes for the purpose of the example ) from bisect import bisect_left as _bisect_left from math import sqrt as _sqrt def get_factors(n): assert isinstance(n, int), "n must be an integer." assert n > 0, "n must be greather than zero." limit = pow(_PRIMES[-1], 2) assert n <= limit, "n is greather then the limit of {0}".format(limit) result = set((1, n)) root = int(_sqrt(n)) primes = [t for t in get_primes_smaller_than(root + 1) if not n % t] result.update(primes) # Add all the primes factors less or equal to root square for t in primes: result.update(get_factors(n/t)) # Add all the factors associted for the primes by using the same process return sorted(result) def get_primes_smaller_than(n): return _PRIMES[:_bisect_left(_PRIMES, n)]
使用set(...)会使代码稍微慢一点，而且只有在检查平方根时才是真正必要的。 这是我的版本：
def factors(num): if (num == 1 or num == 0): return [] f = [1] sq = int(math.sqrt(num)) for i in range(2, sq): if num % i == 0: f.append(i) f.append(num/i) if sq > 1 and num % sq == 0: f.append(sq) if sq*sq != num: f.append(num/sq) return f
if sq*sq != num:条件对于像12这样的数字是必要的，其中平方根不是整数，但是平方根的底部是因子。
请注意，这个版本本身并没有返回数字，但如果你想要的话，这是一个简单的修复。 输出也没有sorting。
我对所有的数字1-200倍进行10000次运行，对所有数字1-5000进行100次。 它胜过我testing过的所有其他版本，包括dansalmo's，Jason Schorn's，oxrock's，agf's，steveha's和eryksun的解决scheme，尽pipeoxrock是迄今为止最接近的。
使用像下面的列表理解那样简单的事情，注意我们不需要testing1和我们试图find的数字：
def factors(n): return [x for x in range(2, n//2+1) if n%x == 0]
参考平方根的使用，比方说我们想要find10的因子。因此sqrt(10) = 4的整数部分因此是range(1, int(sqrt(10))) = [1, 2, 3, 4] ，最多可以testing4个。
除非我错过了我会build议的东西，如果你必须这样做，使用int(ceil(sqrt(x))) 。 当然这会产生很多不必要的函数调用。
一个潜在更有效的algorithm比这里提出的algorithm已经（特别是如果有小的质数n ）。 这里的诀窍就是调整每次发现素因子时需要进行尝试划分的限制 ：
def factors(n): ''' return prime factors and multiplicity of n n = p0^e0 * p1^e1 * ... * pk^ek encoded as res = [(p0, e0), (p1, e1), ..., (pk, ek)] ''' res = [] # get rid of all the factors of 2 using bit shifts mult = 0 while not n & 1: mult += 1 n >>= 1 if mult != 0: res.append((2, mult)) limit = round(sqrt(n)) test_prime = 3 while test_prime <= limit: mult = 0 while n % test_prime == 0: mult += 1 n //= test_prime if mult != 0: res.append((test_prime, mult)) if n == 1: # only useful if ek >= 3 (ek: multiplicity break # of the last prime) limit = round(sqrt(n)) # adjust the limit test_prime += 2 # will often not be prime... if n != 1: res.append((n, 1)) return res
这当然还是审判分庭，没有什么更多的花式。 因此其效率仍然非常有限（尤其是没有小规模的大数字）。
这是python3; 分区/ /应该是你需要适应python 2（ from __future__ import division添加）的唯一的东西。
SymPy中有一个行业强度algorithm叫做factorint ：
>>> from sympy import factorint >>> factorint(2**70 + 3**80) {5: 2, 41: 1, 101: 1, 181: 1, 821: 1, 1597: 1, 5393: 1, 27188665321L: 1, 41030818561L: 1}
这花了一分钟。 它切换方法的鸡尾酒。 请参阅上面链接的文档。
鉴于所有主要因素，所有其他因素可以轻松build立。
请注意，即使被接受的答案被允许运行足够长的时间（即永恒）来计算上述数字，对于一些大数字，它将会失败，例如下面的例子。 这是由于int(n**0.5) 。 例如，当n = 10000000000000079**2 ，我们有
>>> int(n**0.5) 10000000000000078L
由于10000000000000079是一个素数 ，所以接受的答案的algorithm将永远不会find这个因子。 请注意，这不仅仅是一个一个的; 对于更大的数字，它将被closures更多。 出于这个原因，最好避免这种algorithm中的浮点数。
这是我解决问题的方法：
请注意，这将需要更长的时间更大的数字。 唯一的问题是我只知道如何在Python 3.x中编程。 我认为唯一需要改变的是input（）到raw_input（）。
# Sets the number num = int(input("Enter number to be tested.")) for i in range(1,num): # Tests all numbers from 1 to the num while (num % i) == 0: ''' If the remainder of the number when it is divided by i is 0''' print(i) # Prints i break # Stops it from repeating one number infinitely else: # After the previous process if done, do this print("Finished") # Says that the process is finished input ("Press return/enter to close the program") ''' Closes the program after pressing enter'''
我认为可读性和速度@ oxrock的解决scheme是最好的，所以这里是python 3 +的代码重写：
def num_factors(n): results = set() for i in range(1, int(n**0.5) + 1): if n % i == 0: results.update([i,int(n/i)]) return results
如果不使用reduce（）而不是Python3中的内置函数：
def factors(n): return list(sorted(set([f(x) for x in range(1, int(n**0.5) + 1) if not n % x for f in (lambda x: x, lambda x: n // x)])))
from functools import reduce def factors(n): return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))) if __name__ == "__main__": n = int(input("enter the number to get factors")) fact = list(factors(n)) for x in fact: print(x)
对于高达10 ** 16（甚至更多），这是一个快速纯Python 3.6解决scheme，
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))
