得到一个数的所有除数的最好方法是什么？

这是一个非常愚蠢的方法:

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

我希望得到的结果和这个类似，但是我想要一个更聪明的算法(这个算法太慢而且太笨了: -)

我可以很快找到质因子和它们的多样性。 我有一个发电机，用这种方式产生因子:

(factor1，multiplicity 1)
(factor 2，multiplicity 2)
(factor 3，multiplicity 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: 不要再说这是 这个文章的复制品。计算一个给定数字的除数并不需要计算所有的除数。这是一个不同的问题，如果你认为它不是，那么在维基百科上寻找“除数函数”。在发帖之前阅读问题和答案，如果你不明白什么是主题，只是不要添加没有用的和已经给出的答案。

204375 次浏览
小开

要扩展 Shimi 所说的内容，您应该只运行从1到 n 的平方根的循环。然后，为了找到这个对，执行 n / i，这将覆盖整个问题空间。

正如前面提到的，这是一个 NP 问题，或者说是一个“难”问题。用尽全力的搜索，你正在做的方式，是最好的，因为它得到了保证的答案。这个事实被加密算法和类似的东西用来帮助保护它们。如果有人解决了这个问题，我们目前所有的“安全”通信都会变得不安全。

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]
小开
最佳答案

考虑到你的 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的效率。

小开

我喜欢格雷格的解决方案，但我希望它更像蟒蛇。 我觉得它会更快，更易读; 所以经过一段时间的编码，我想出了这个。

制作列表的笛卡儿积需要前两个函数。 而且在出现这种问题时可以重复使用。 顺便说一下，我必须自己编程，如果有人知道这个问题的标准解决方案，请随时与我联系。

“ FactorGenerator”现在返回一个字典。然后字典被输入到“除数”中，“除数”首先用它生成一个列表，其中每个列表都是 p ^ n 与 p’形式的因子的列表。 然后我们对这些列表进行笛卡儿积，最后使用 Greg 的解生成除数。 我们把它们分类，然后归还。

我测试了一下，它似乎比之前的版本要快一些。我测试它作为一个更大的程序的一部分，所以我真的不能说多少是更快的，虽然。

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)

附言。 这是我第一次发布到堆栈溢出。 我期待着任何反馈。

小开

改编自 代码审查，这里是一个与 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))
小开

假设 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
小开 
return [x for x in range(n+1) if n/x==int(n/x)]
小开

这是我的解决办法。它看起来很蠢，但是很好用，我试图找到所有合适的除数，所以循环从 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
小开

老问题了，但我的看法是:

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

注意: 对于支持的语言，这可能是尾递归。

小开

我认为你可以停在 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开始

Divisors of a 28

因此，在所有迭代的最后，当我将商和除数加入到我的列表中时，所有28的除数都被填充。

资料来源: 如何确定一个数的除数

小开

虽然已经有很多解决方案，但我还是要把这个贴出来:)

这个是:

  • 可读
  • 太短了
  • 自包含，复制和粘贴准备
  • 快速(在有许多素因子和除数的情况下，比公认的解快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
小开

在纯 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))
小开

如果您只关心使用列表理解，而对您来说没有其他任何事情！

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)
小开

一个说明性的 Python 俏皮话:

from itertools import chain
from math import sqrt


def divisors(n):
return set(chain.from_iterable((i,n//i) for i in range(1,int(sqrt(n))+1) if n%i == 0))

但更好的方法是，使用 symy:

from sympy import divisors
小开

如果你的电脑有成吨的内存，一条粗糙的单行线可以快得足够麻木:

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。

小开

我通过生成器函数的解决方案是:

def divisor(num):
for x in range(1, num + 1):
if num % x == 0:
yield x
while True:
yield None
小开

尝试计算给定数字的平方根，然后循环范围(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)
小开 
def divisorGen(n): v = n last = [] for i in range(1, v+1) : if n % i == 0 : last.append(i)
小开

我不明白为什么这个问题有这么多复杂的解决方案。

以下是我对此的看法:

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))

提交答案