在 Python 中查找数字的所有因数的最有效方法是什么？[关闭]
- 2025-01-14 08:50:00
- admin 原创
- 130
问题描述：
有人能向我解释一下在 Python（2.7）中找出一个数字的所有因数的有效方法吗？
我可以创建一个算法来做到这一点，但我认为它的编码很差，并且需要很长时间才能对大量数字产生结果。
解决方案 1：
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)))
这将非常快速地返回一个数字的所有因数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删除其中一个。
解决方案 2：
@agf 提出的解决方案很棒，但对于任意奇数，通过检查奇偶性，运行时间可以缩短约 50% 。由于奇数的因数本身总是奇数，因此在处理奇数时无需检查这些因数。
我自己也刚开始解答欧拉计划的难题。在一些问题中，除数检查在两个嵌套循环中调用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 = 范围（1,100000,1000）（仅限奇数）
X = 范围（2,100000,100）（仅限偶数）
X = 范围（1,100000,1001）（交替奇偶校验）
解决方案 3：
SymPy 中有一个业界强度的算法，称为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}
这花了不到一分钟的时间。它在多种方法之间切换。请参阅上面链接的文档。
给定所有主要因素，可以轻松构建所有其他因素。
请注意，即使允许接受的答案运行足够长的时间（即永恒）以分解上述数字，对于一些大数字，它也会失败，例如以下示例。这是由于不严谨的int(n**0.5)。例如，当时n = 10000000000000079**2，我们有
>>> int(n**0.5)
10000000000000078L
由于10000000000000079 是素数，因此接受答案的算法永远找不到这个因数。请注意，它不仅仅是偏差 1；对于较大的数字，偏差会更大。因此，最好避免在此类算法中使用浮点数。
解决方案 4：
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) 命令下运行了三次并保留了最佳时间。
减少版本：11.58秒
itertools 版本：11.49 秒
棘手版本：11.12 秒
请注意，itertools 版本正在构建一个元组并将其传递给 flatten_iter()。如果我将代码改为构建列表，速度会稍微变慢：
iterools（列表）版本：11.62 秒
我认为棘手的生成器函数版本是 Python 中最快的。但它实际上并不比 Reduce 版本快多少，根据我的测量，大约快 4%。
解决方案 5：
这是@agf 解决方案的替代方法，它以更 Python 风格实现相同的算法：
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 中均有效，无需导入，并且可读性更强。我尚未测试此方法的性能，但渐进地看，它应该是相同的，如果性能是一个严重的问题，那么这两种解决方案都不是最佳的。
解决方案 6：
对于 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))
解决方案 7：
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
解决方案 8：
寻找数字因数的最简单方法：
def factors(x):
return [i for i in range(1,x+1) if x%i==0]
解决方案 9：
我已经用 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
按照说明，您必须导入 math 进行测试，但将 math.sqrt(n) 替换为 n**.5 也同样有效。我不想浪费时间检查重复项，因为无论如何，集合中都不能存在重复项。
解决方案 10：
我最近开发了一种新的整数分解方法，称为平滑子和搜索 (SSS)。这是我在 Python 中的实现：https ://github.com/sbaresearch/smoothsubsumsearch
它可以在大约 0.2 秒内分解 30 位数字，在大约 2 秒内分解 40 位数字，在大约 30 秒内分解 50 位数字，在大约 200 秒内分解 60 位数字，在大约 3000 秒内分解 70 位数字。与 sympy 中的自初始化二次筛实现（这是我能找到的最高效的 Python 二次筛实现）相比，它的运行速度大约快 5 到 7 倍。SSS 的详细描述如下：https: //arxiv.org/abs/2301.10529
解决方案 11：
进一步改进了 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) 的排序列表；而是在 l2 上使用 list.reverse() 来获取复杂度为 O(n) 的列表，这样速度要快得多。（这就是 python 的实现方式。）在 l2.reverse() 之后，可以将 l2 附加到 l1 以获取因子的排序列表。
注意，l1 包含增加的i -s。l2 包含减少的q -s。这就是使用上述想法的原因。
解决方案 12：
这是另一个不使用 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], []))
解决方案 13：
一定要抓住大于sqrt(number_to_factor)不寻常数字的数字，例如 99，它有 3311 和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
解决方案 14：
如果您想使用素数来加快速度，这里有一个例子。这些列表很容易在互联网上找到。我在代码中添加了注释。
# 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)]
解决方案 15：
一种可能比这里已经介绍的算法更有效的算法（特别是如果 中有小的素因数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）。
解决方案 16：
我找到了一个使用 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]
解决方案 17：
如果您不想使用任何库，那么我认为这是最简单的方法：
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
解决方案 18：
虽然问题说的是 Python (2.7)，但人们可能对使用 Numpy 的这个简单解决方案感兴趣。
import numpy as np
t=np.arange(2,n,1)
t[n%t==0]
这不会返回1数字本身n。因此，如果是素数，它将返回一个空数组n。
解决方案 19：
我有点惊讶我找不到形式为整数素数分解的简单实现(p1 ** e1) * (p2 ** e2) ...，所以我决定自己写一个。
from collections import defaultdict
from itertools import count
def factorize(n):
factors = defaultdict(int)
for i in count(2):
while n % i == 0:
factors[i] += 1
n /= i
if n == 1:
return factors
此函数返回一个字典，其中键是素因数，值是指数。例如：
>>> factorize(608)
defaultdict(<class 'int'>, {2: 5, 19: 1})
>>> factorize(1152)
defaultdict(<class 'int'>, {2: 7, 3: 2})
>>> factorize(1088)
defaultdict(<class 'int'>, {2: 6, 17: 1})
这显然不是最有效的实现——因为它会遍历整个自然数集，而不是直接寻找素数——但对于相对较小的值来说已经足够了，并且足够简单，可以很容易地理解。
解决方案 20：
使用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
对于像 12 这样的数字，这个if sq*sq != num:条件是必要的，其中平方根不是整数，但平方根的下限是一个因子。
请注意，此版本不返回数字本身，但如果您需要，这很容易解决。输出也未排序。
我计时它在 1-200 的所有数字上运行了 10000 次，并在 1-5000 的所有数字上运行了 100 次。它的表现优于我测试过的所有其他版本，包括 dansalmo、Jason Schorn、oxrock、agf、steveha 和 eryksun 的解决方案，尽管 oxrock 的解决方案是最接近的。
解决方案 21：
当我看到这个问题时，我感到非常惊讶，即使 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
解决方案 22：
你的最大因子不超过你的数字，所以，假设
def factors(n):
factors = []
for i in range(1, n//2+1):
if n % i == 0:
factors.append (i)
factors.append(n)
return factors
瞧！
解决方案 23：
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.
解决方案 24：
我们可以使用以下 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)]
此函数返回列表中给定数字的所有因数。
解决方案 25：
使用一些简单的东西，如下面的列表推导，注意我们不需要测试 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)))。当然，这会产生许多不必要的函数调用。
解决方案 26：
我认为就可读性和速度而言@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
解决方案 27：
循环直到在元组的 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]
解决方案 28：
考虑到该数字是正整数，您可以使用这种方法：
number = int(input("Enter a positive number to find factors: "))
factor = [num for num in range(1,number+1) if number % num == 0]
for fac in factor: print(f"{fac} is a factor of {number}")
解决方案 29：
Python 3.5在标准模块中添加了一个gcd()函数math：
math.gcd(*integers)返回指定整数参数的最大公约数。如果任何参数非零，则返回值为所有参数的最大正整数除数。如果所有参数均为零，则返回值为
0。gcd()不带参数则返回0。
解决方案 30：
我认为这是最简单的方法：
x = 23
i = 1
while i <= x:
if x % i == 0:
print("factor: %s"% i)
i += 1
