获得一个数字的所有除数的最佳方法是什么？
- 2025-02-21 08:48:00
- admin 原创
- 26
问题描述：
这是一个非常愚蠢的方法：
def divisorGenerator(n):
for i in xrange(1,n/2+1):
if n%i == 0: yield i
yield n
我想要得到的结果与这个类似，但我想要一个更智能的算法（这个算法太慢太笨了:-)
我可以足够快地找到素因数及其重数。我有一个以这种方式生成因子的生成器：
(因子 1，多重性 1)
(因子 2，多重性 2)
(因子 3，多重性 3)
等等...
即输出
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
更新：非常感谢 Greg Hewgill 和他的“智能方法” :) 用他的方法计算 100000000 的所有除数只花了 0.01 秒，而在我的计算机上用笨方法则花了 39 秒，非常酷 :D
更新 2：不要再说这是这篇文章的重复了。计算给定数字的除数的数量并不需要计算所有除数。这是一个不同的问题，如果你认为不是，那么请在维基百科上查找“除数函数”。在发帖之前阅读问题和答案，如果你不明白主题是什么，就不要添加无用和已经给出的答案。
解决方案 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
该算法的整体效率将完全取决于的效率factorGenerator。
解决方案 2：
为了扩展 Shimi 所说的内容，您应该只运行从 1 到 n 的平方根的循环。然后要找到对，请执行n / i，这将覆盖整个问题空间。
正如之前所指出的，这是一个 NP，即“困难”问题。穷举搜索，也就是你正在做的方式，对于保证答案来说，几乎是最好的办法了。加密算法等利用这个事实来帮助保护它们。如果有人能解决这个问题，那么我们目前大多数（如果不是全部）“安全”通信都会变得不安全。
Python代码：
import math
def divisorGenerator(n):
large_divisors = []
for i in range(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]
解决方案 3：
我认为你可以停止在math.sqrt(n)n/2 而不是 n/2。
我会给你举个例子，这样你就能轻松理解。现在的除数将sqrt(28)是6。所以如果我停在 6，那么我就能得到所有的除数。怎么做？5.29`ceil(5.29)`
先看代码，再看图片：
import math
def divisors(n):
divs = [1]
for i in range(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 的除数都已填充。
来源：如何确定一个数字的除数
解决方案 4：
尽管已经有很多解决方案，但我真的必须发布这个:)
这是：
可读
短的
自成体系，可复制粘贴
快速（在有大量素因数和除数的情况下，比公认的解决方案快 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:
factors[i] = factors.get(i, 0) + 1
nn //= i
i += 1
if nn > 1:
factors[nn] = factors.get(nn, 0) + 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
解决方案 5：
一个说明性的 Pythonic 单行代码：
from itertools import chain
from math import isqrt
def divisors(n):
return set(chain.from_iterable((i,n//i) for i in range(1,isqrt(n)+1) if n%i == 0))
但更好的是，只需使用 sympy：
from sympy import divisors
解决方案 6：
我喜欢 Greg 的解决方案，但我希望它更像 Python。我觉得它会更快、更易读；所以经过一段时间的编码后，我提出了这个。
前两个函数是生成列表的笛卡尔积所必需的。每当出现此问题时都可以重复使用。顺便说一句，我不得不自己编写这个程序，如果有人知道此问题的标准解决方案，请随时与我联系。
“Factorgenerator” 现在返回一个字典。然后，该字典被输入到“divisors”中，divisors 使用它首先生成一个列表列表，其中每个列表都是形式为 p^n 且 p 为素数的因子列表。然后我们计算这些列表的笛卡尔积，最后使用 Greg 的解决方案生成除数。我们对它们进行排序，然后返回它们。
我测试了它，它似乎比以前的版本快一点。我把它作为一个更大的程序的一部分进行测试，所以我不能确切地说它快了多少。
彼得罗·斯佩罗尼 (pietrosperoni dot it)
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 这是我第一次在 stackoverflow 上发帖。我期待任何反馈。
解决方案 7：
这是在纯 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((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))
解决方案 8：
如果你的电脑有大量内存，使用 numpy 只需一行就可以足够快：
N = 10000000; tst = np.arange(1, N); tst[np.mod(N, tst) == 0]
Out:
array([ 1, 2, 4, 5, 8, 10, 16,
20, 25, 32, 40, 50, 64, 80,
100, 125, 128, 160, 200, 250, 320,
400, 500, 625, 640, 800, 1000, 1250,
1600, 2000, 2500, 3125, 3200, 4000, 5000,
6250, 8000, 10000, 12500, 15625, 16000, 20000,
25000, 31250, 40000, 50000, 62500, 78125, 80000,
100000, 125000, 156250, 200000, 250000, 312500, 400000,
500000, 625000, 1000000, 1250000, 2000000, 2500000, 5000000])
在我较慢的电脑上花费的时间不到 1 秒。
解决方案 9：
改编自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))
解决方案 10：
老问题了，但我的看法如下：
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
注意：对于支持的语言，这可能是尾部递归。
解决方案 11：
#slow but pretty
return [x for x in range(1,n+1) if n/x==int(n/x)]
解决方案 12：
假设函数返回nfactors的因数（例如返回列表 [2, 2, 3, 5]），下面是一个计算n的除数的函数：factors(60)
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
解决方案 13：
这是我的解决方案。它看起来很愚蠢，但效果很好……我试图找到所有适当的除数，所以循环从 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
解决方案 14：
如果您只关心使用列表推导，而其他任何事情对您来说都不重要！
from itertools import combinations
from functools import reduce
def get_devisors(n):
f = [f for f,e in list(factorGenerator(n)) for i in range(e)]
fc = [x for l in range(len(f)+1) for x in combinations(f, l)]
devisors = [1 if c==() else reduce((lambda x, y: x * y), c) for c in set(fc)]
return sorted(devisors)
解决方案 15：
我通过生成器函数解决的解决方案是：
def divisor(num):
for x in range(1, num + 1):
if num % x == 0:
yield x
while True:
yield None
解决方案 16：
尝试计算给定数字的平方根，然后循环范围（1，square_root + 1）。
number = int(input("Enter a Number: "))
square_root = round(number ** (1.0 / 2))
print(square_root)
divisor_list = []
for i in range(1,square_root+1):
if number % i == 0: # Check if mod return 0 if yes then append i and number/i in the list
divisor_list.append(i)
divisor_list.append(int(number/i))
print(divisor_list)
解决方案 17：
def divisorGen(n): v = n last = [] for i in range(1, v+1) : if n % i == 0 : last.append(i)
解决方案 18：
我不明白为什么这个问题有这么多复杂的解决方案。
以下是我的看法：
def divisors(n):
lis =[1]
s = math.ceil(math.sqrt(n))
for g in range(s,1, -1):
if n % g == 0:
lis.append(g)
lis.append(int(n / g))
return (set(lis))
解决方案 19：
我在这里找到了最快的算法。
但首先，您要从质因数分解开始，这在编码上相当简单。
相关推荐
热门文章
项目管理软件有哪些？
- 2025年20款好用的项目管理软件推荐，项目管理提效的20个工具和技巧
- 2024年开源项目管理软件有哪些？推荐5款好用的项目管理工具
- 2024年常用的项目管理软件有哪些？推荐这10款国内外好用的项目管理工具
- 项目管理软件有哪些？推荐7款超好用的项目管理工具
- 项目管理软件有哪些最好用？推荐6款好用的项目管理工具
- 项目管理软件哪个最好用？盘点推荐5款好用的项目管理工具
- 项目管理软件排行榜：2024年项目经理必备5款开源项目管理软件汇总
- 项目管理必备:盘点2024年13款好用的项目管理软件
- 项目管理软件有哪些，盘点推荐国内外超好用的7款项目管理工具
- 2024项目管理软件排行榜（10类常用的项目管理工具全推荐）
热门标签
云禅道AD
