這是非常愚蠢的方式：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輸出：124510202550100更新：非常感謝格雷格·休吉爾（Greg Hewgill）和他的“聰明之道” :)計算100000000的所有除數，而他的方式與我的機器上愚蠢的方式所用的39分相差0.01s。更新2：別說這是這篇文章的重復。計算給定數的除數的數量不需要計算所有除數。這是一個不同的問題，如果您認為不是這樣，那么請在Wikipedia上查找“除數函數”。在發帖之前，請先閱讀問題和答案，如果您不明白主題是什么，請僅添加沒有用的已經給出的答案。
3 回答
心有法竹
TA貢獻1866條經驗 獲得超5個贊
給定您的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的效率。
陪伴而非守候
TA貢獻1757條經驗 獲得超8個贊
您應該只在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]
慕仙森
TA貢獻1827條經驗 獲得超8個贊
盡管已經有很多解決方案，但我確實必須發布此內容：）
快速（在有很多主要因素和因數的情況下，比公認的解決方案快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
添加回答
舉報
0/150
提交
取消