这是非常愚蠢的方式:
def divisorGenerator(n):
for i in xrange(1,n/2+1):
if n%i == 0: yield i
yield n
我想得到的结果类似于这个,但我想要一个更聪明的算法(这个太慢和愚蠢了:-)
我可以足够快地找到素数因子及其多样性。我有一个以这种方式生成因子的生成器:
(factor1,multiplicity1) (factor2,multiplicity2) (factor3,multiplicity3) 等等...
即输出
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的除数用他的方式对着我的机器上的愚蠢方式的39s,非常酷:D
更新2:停止说这是this帖子的副本。计算给定数的除数数不需要计算所有除数。这是一个不同的问题,如果你认为它不是在维基百科上寻找“除数函数”。在发布之前阅读问题和答案,如果你不明白什么是主题,只是不添加没有用的已经给出的答案。
鉴于您的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的效率。
假设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
这是我的解决方案。它似乎很愚蠢,但效果很好......我试图找到所有适当的除数,所以循环从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
如果您只关心使用列表推导而且其他任何事情都不重要!
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)
return [x for x in range(n+1) if n/x==int(n/x)]
对我来说,这很好,也很干净(Python 3)
def divisors(number):
n = 1
while(n<number):
if(number%n==0):
print(n)
else:
pass
n += 1
print(number)
不是很快但是你可以逐行返回除数,你也可以做list.append(n)和list.append(数字)如果你真的想要
为了扩展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]
我想你可以停在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
开始
所以在所有迭代结束时,因为我已将商和除数添加到我的列表中,所有28的除数都被填充。
虽然已经有很多解决方案,但我真的要发布这个:)
这个是:
码:
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
我喜欢Greg解决方案,但我希望它更像python。我觉得它会更快,更具可读性;所以在经过一段时间的编码之后,我就出来了。
需要前两个函数来制作列表的笛卡尔积。并且只要出现这个问题就可以重复使用。顺便说一句,我必须自己编程,如果有人知道这个问题的标准解决方案,请随时与我联系。
“Factorgenerator”现在返回一个字典。然后将字典输入“除数”,使用它来首先生成列表列表,其中每个列表是具有p prime的形式p ^ n的因子列表。然后我们制作这些列表的笛卡尔积,我们最终使用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)
附:这是我第一次发布到stackoverflow。我期待着任何反馈。
改编自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))
老问题,但这是我的看法:
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
注意:对于支持的语言,这可能是尾递归。
这是一种智能而快速的方法,可以在纯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))
我只想添加一个略微修改版的Anivarth(因为我相信它是最pythonic)以供将来参考。
from math import sqrt
def divisors(n):
divs = {1,n}
for i in range(2,int(sqrt(n))+1):
if n%i == 0:
divs.update((i,n//i))
return divs