有人可以向我解释一种在 Python（2.7）中找到数字的所有因子的有效方法吗？
我可以创建一个算法来做到这一点，但我认为它的编码很差，并且需要很长时间才能产生大量的结果。
问问题
225978 次
27 回答
304
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)))
这将很快返回一个 number 的所有因数n。
为什么以平方根为上限？
sqrt(x) * sqrt(x) = x. 因此，如果这两个因素相同，它们都是平方根。如果你让一个因素变大，你必须让另一个因素变小。这意味着两者之一将始终小于或等于sqrt(x)，因此您只需搜索到该点即可找到两个匹配因子之一。然后您可以x / fac1使用fac2.
reduce(list.__add__, ...)正在获取一些小列表并将[fac1, fac2]它们连接在一起形成一个长列表。
[i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0如果除以较小的余数为零，则返回一对因子（n它也不需要检查较大的因子；它只需通过除以n较小的因子即可。）
set(...)外部正在消除重复项，这仅发生在完美的正方形中。对于n = 4，这将返回2两次，因此set摆脱其中一个。
于 2011-07-23T12:04:32.007 回答
70
@agf 提出的解决方案很棒，但是通过检查奇偶校验可以将任意奇数的运行时间缩短约 50% 。由于奇数的因子本身总是奇数，因此在处理奇数时无需检查这些因素。
我刚刚开始自己解决Project Euler难题。在某些问题中，在两个嵌套循环中调用除数检查for，因此该函数的性能至关重要。
将这一事实与 agf 的出色解决方案相结合，我最终得到了这个函数：
from functools import reduce
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），此更改带来的额外开销可能会导致函数花费更长的时间。
我进行了一些测试以检查速度。下面是使用的代码。为了产生不同的情节，我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 = range(1,100000,1000)（仅奇数）
X = range(2,100000,100)（仅偶数）
X = range(1,100000,1001)（交替奇偶校验）
于 2013-10-24T23:57:04.697 回答
31
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编译，然后在time(1)命令下跑了3次，保持最佳时间。
- 减少版本：11.58 秒
- itertools 版本：11.49 秒
- 棘手的版本：11.12 秒
请注意，itertools 版本正在构建一个元组并将其传递给 flatten_iter()。如果我更改代码以构建列表，它会稍微减慢：
- iterools（列表）版本：11.62 秒
我相信棘手的生成器函数版本是 Python 中最快的版本。但它并没有比 reduce 版本快多少，根据我的测量大约快 4%。
于 2011-08-02T08:57:08.630 回答
17
There is an industry-strength algorithm in SymPy called 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}
This took under a minute. It switches among a cocktail of methods. See the documentation linked above.
Given all the prime factors, all other factors can be built easily.
Note that even if the accepted answer was allowed to run for long enough (i.e. an eternity) to factor the above number, for some large numbers it will fail, such the following example. This is due to the sloppy int(n**0.5). For example, when n = 10000000000000079**2, we have
>>> int(n**0.5)
10000000000000078L
Since 10000000000000079 is a prime, the accepted answer's algorithm will never find this factor. Note that it's not just an off-by-one; for larger numbers it will be off by more. For this reason it's better to avoid floating-point numbers in algorithms of this sort.
于 2017-05-17T05:47:08.807 回答
16
这是@agf 解决方案的替代方案，它以更pythonic 的风格实现相同的算法：
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)
)
该解决方案在 Python 2 和 Python 3 中均适用，无需导入，并且更具可读性。我还没有测试过这种方法的性能，但它应该是一样的，如果性能是一个严重的问题，那么这两种解决方案都不是最优的。
于 2016-08-07T19:42:58.573 回答
13
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
于 2011-07-23T13:10:10.003 回答
13
对于 n 高达 10**16（甚至可能更多），这是一个快速的纯 Python 3.6 解决方案，
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((n-i*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))
于 2017-10-09T00:22:06.580 回答
12
求数的因数的最简单方法：
def factors(x):
return [i for i in range(1,x+1) if x%i==0]
于 2019-05-13T07:09:39.407 回答
8
我已经使用 timeit 尝试了大多数这些精彩的答案，以将它们的效率与我的简单功能进行比较，但我经常看到我的表现优于此处列出的那些。我想我会分享它，看看大家的想法。
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
正如它所写的那样，你必须导入数学来测试，但是用 n**.5 替换 math.sqrt(n) 应该也可以。我不会浪费时间检查重复项，因为无论如何重复项都不能存在于集合中。
于 2014-11-21T00:57:42.947 回答
6
进一步改进 afg & eryksun 的解决方案。以下代码在不改变运行时渐近复杂度的情况下返回所有因子的排序列表：
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) 的复杂性；在需要 O(n) 复杂度的 l2 上使用 list.reverse() 要快得多。（这就是 python 的制作方式。）在 l2.reverse() 之后，可以将 l2 附加到 l1 以获取排序后的因子列表。
请注意，l1 包含i -s，它们正在增加。l2 包含正在减少的q -s。这就是使用上述想法的原因。
于 2012-12-22T02:19:26.393 回答
5
这是另一个没有 reduce 的替代方案，它在大量数据中表现良好。它用于sum展平列表。
def factors(n):
return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))
于 2013-11-08T02:45:19.473 回答
4
一定要抓住比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
于 2013-01-25T11:31:08.280 回答
2
这是一个示例，如果您想使用素数来加快速度。这些列表很容易在 Internet 上找到。我在代码中添加了注释。
# 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)]
于 2015-02-20T06:22:18.667 回答
2
一种可能比这里已经介绍的算法更有效的算法（特别是如果 中存在小的素因子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。
于 2017-05-13T15:43:43.000 回答
2
如果您不想使用任何库，那么我认为这是最简单的方法：
def factors(n):
l = [] # empty list
# appending the factors in the list
for i in range(1,n+1):
if n%i==0:
l.append(i)
return l
于 2021-07-05T14:03:40.087 回答
1
当我看到这个问题时，我感到非常惊讶，即使 numpy比 python 循环快得多，也没有人使用过 numpy。通过使用 numpy 实现 @agf 的解决方案，结果平均速度提高了8 倍。我相信如果你在 numpy 中实现了一些其他的解决方案，你会得到惊人的时间。
这是我的功能：
import numpy as np
def b(n):
r = np.arange(1, int(n ** 0.5) + 1)
x = r[np.mod(n, r) == 0]
return set(np.concatenate((x, n / x), axis=None))
请注意，x 轴的数字不是函数的输入。函数的输入是 x 轴上的数字减去 1 的 2。所以输入为 10 的地方是 2**10-1 = 1023
于 2018-08-21T10:47:30.993 回答
1
我在 python 中找到了一个使用 cypari 库的简单解决方案。这是一个链接！
import cypari
def get_divisors(n):
divisors = cypari.pari('divisors({})'.format(n))
return divisors
print(get_divisors(24))
输出
[1, 2, 3, 4, 6, 8, 12, 24]
于 2021-07-06T08:41:05.530 回答
1
你的最大因子不超过你的数字，所以，让我们说
def factors(n):
factors = []
for i in range(1, n//2+1):
if n % i == 0:
factors.append (i)
factors.append(n)
return factors
瞧！
于 2018-12-07T09:50:41.190 回答
1
import math
'''
I applied finding prime factorization to solve this. (Trial Division)
It's not complicated
'''
def generate_factors(n):
lower_bound_check = int(math.sqrt(n)) # determine lowest bound divisor range [16 = 4]
factors = set() # store factors
for divisors in range(1, lower_bound_check + 1): # loop [1 .. 4]
if n % divisors == 0:
factors.add(divisors) # lower bound divisor is found 16 [ 1, 2, 4]
factors.add(n // divisors) # get upper divisor from lower [ 16 / 1 = 16, 16 / 2 = 8, 16 / 4 = 4]
return factors # [1, 2, 4, 8 16]
print(generate_factors(12)) # {1, 2, 3, 4, 6, 12} -> pycharm output
Pierre Vriens hopefully this makes more sense. this is an O(nlogn) solution.
于 2018-12-08T19:08:59.023 回答
1
使用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 这样的数字是必要的，其中平方根不是整数，但平方根的下限是一个因子。
请注意，此版本本身不会返回数字，但如果您愿意，这很容易解决。输出也没有排序。
我计时它在所有数字 1-200 上运行 10000 次，在所有数字 1-5000 上运行 100 次。它优于我测试过的所有其他版本，包括 dansalmo 的、Jason Schorn 的、oxrock 的、agf 的、steveha 的和 eryksun 的解决方案，尽管 oxrock 是迄今为止最接近的。
于 2015-09-02T20:16:26.177 回答
0
使用像下面的列表推导一样简单的东西，注意我们不需要测试 1 和我们试图找到的数字：
def factors(n):
return [x for x in range(2, n//2+1) if n%x == 0]
关于平方根的使用，假设我们想要找到 10 的因数。sqrt(10) = 4因此range(1, int(sqrt(10))) = [1, 2, 3, 4]和测试高达 4 的整数部分显然错过了 5。
除非我遗漏了我会建议的内容，否则如果您必须这样做，请使用int(ceil(sqrt(x))). 当然，这会产生很多不必要的函数调用。
于 2013-03-03T19:13:08.853 回答
0
循环，直到在元组的 x 或 v 中找到重复项，其中 x 是分母，v 是结果。
number=30
tuple_list=[]
for i in np.arange(1,number):
if number%i==0:
other=int(number/i)
if any([(x,v) for (x,v) in tuple_list if (i==x) or (i==v)])==True:
break
tuple_list.append((i,other))
flattened = [item for sublist in tuple_list for item in sublist]
print(sorted(flattened))
输出
[1, 2, 3, 5, 6, 10, 15, 30]
于 2021-06-04T20:04:20.747 回答
0
我认为对于可读性和速度@oxrock 的解决方案是最好的，所以这里是为 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
于 2017-03-12T17:19:34.080 回答
0
虽然问题是 Python (2.7)，但人们可能会对这个使用 Numpy 的简单解决方案感兴趣。
import numpy as np
t=np.arange(2,n,1)
t[n%t==0]
这不会返回1，也不会返回数字本身n。n因此，如果是素数，它将返回一个空数组。
于 2022-01-31T10:41:00.993 回答
0
我们可以使用下面的 lambda 函数，
factor = lambda x:[(ele,x/ele) for ele in range(1,x//2+1) if x%ele==0 ]
因素(10)
输出：[(1, 10.0), (2, 5.0), (5, 2.0)]
此函数返回列表中给定数字的所有因子。
于 2021-12-10T15:11:01.567 回答
-1
import 'dart:math';
generateFactorsOfN(N){
//determine lowest bound divisor range
final lowerBoundCheck = sqrt(N).toInt();
var factors = Set<int>(); //stores factors
/**
* Lets take 16:
* 4 = sqrt(16)
* start from 1 ... 4 inclusive
* check mod 16 % 1 == 0? set[1, (16 / 1)]
* check mod 16 % 2 == 0? set[1, (16 / 1) , 2 , (16 / 2)]
* check mod 16 % 3 == 0? set[1, (16 / 1) , 2 , (16 / 2)] -> unchanged
* check mod 16 % 4 == 0? set[1, (16 / 1) , 2 , (16 / 2), 4, (16 / 4)]
*
* ******************* set is used to remove duplicate
* ******************* case 4 and (16 / 4) both equal to 4
* return factor set<int>.. this isn't ordered
*/
for(var divisor = 1; divisor <= lowerBoundCheck; divisor++){
if(N % divisor == 0){
factors.add(divisor);
factors.add(N ~/ divisor); // ~/ integer division
}
}
return factors;
}
于 2018-12-08T09:31:45.200 回答
-5
我认为这是最简单的方法：
x = 23
i = 1
while i <= x:
if x % i == 0:
print("factor: %s"% i)
i += 1
于 2018-08-11T08:06:41.513 回答