第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全，請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問(wèn)題，去搜搜看，總會(huì)有你想問(wèn)的

得到一個(gè)數(shù)的所有除數(shù)的最佳方法是什么？

得到一個(gè)數(shù)的所有除數(shù)的最佳方法是什么？

這是非常愚蠢的方式：def divisorGenerator(n):    for i in xrange(1,n/2+1):        if n%i == 0: yield i    yield n我想要得到的結(jié)果與此類似，但是我想要一種更智能的算法（這個(gè)算法太慢而且太笨了:-)我可以很快找到主要因素及其多樣性。我有一個(gè)生成器以這種方式生成因子：（factor1，multiplicity1）（factor2，multiplicity2）（factor3，multiplicity3）等等...即輸出for i in factorGenerator(100):    print i是：(2, 2)(5, 2)我不知道這對(duì)我想做的事情有多大幫助（我為其他問(wèn)題編寫了代碼），無(wú)論如何，我都希望有一種更聰明的制作方法for i in divisorGen(100):    print i輸出：124510202550100更新：非常感謝格雷格·休吉爾（Greg Hewgill）和他的“聰明之道” :)計(jì)算100000000的所有除數(shù)，而他的方式與我的機(jī)器上愚蠢的方式所用的39分相差0.01s。更新2：別說(shuō)這是這篇文章的重復(fù)。計(jì)算給定數(shù)的除數(shù)的數(shù)量不需要計(jì)算所有除數(shù)。這是一個(gè)不同的問(wèn)題，如果您認(rèn)為不是這樣，那么請(qǐng)?jiān)赪ikipedia上查找“除數(shù)函數(shù)”。在發(fā)帖之前，請(qǐng)先閱讀問(wèn)題和答案，如果您不明白主題是什么，請(qǐng)僅添加沒(méi)有用的已經(jīng)給出的答案。
查看完整描述

3 回答

?
心有法竹

TA貢獻(xiàn)1866條經(jīng)驗(yàn) 獲得超5個(gè)贊

給定您的factorGenerator函數(shù)，這是一個(gè)應(yīng)該工作的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的效率。


查看完整回答
反對(duì) 回復(fù) 2019-11-07
?
陪伴而非守候

TA貢獻(xiàn)1757條經(jīng)驗(yàn) 獲得超8個(gè)贊

您應(yīng)該只在1到n的平方根之間運(yùn)行循環(huán)。然后找到對(duì)，執(zhí)行n / i，這將覆蓋整個(gè)問(wèn)題空間。


還應(yīng)指出的是，這是一個(gè)NP或“困難”的問(wèn)題。窮舉搜索（您正在執(zhí)行的方式）與保證答案的效果差不多。加密算法等使用此事實(shí)來(lái)幫助保護(hù)它們。如果有人要解決這個(gè)問(wèn)題，那么我們目前大多數(shù)的“安全”通信，即使不是全部，也會(huì)變得不安全。


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

應(yīng)該輸出如下列表：


[1、2、4、5、10、20、25、50、100]


查看完整回答
反對(duì) 回復(fù) 2019-11-07
?
慕仙森

TA貢獻(xiàn)1827條經(jīng)驗(yàn) 獲得超8個(gè)贊

盡管已經(jīng)有很多解決方案，但我確實(shí)必須發(fā)布此內(nèi)容：）

快速（在有很多主要因素和因數(shù)的情況下，比公認(rèn)的解決方案快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


查看完整回答
反對(duì) 回復(fù) 2019-11-07
  • 3 回答
  • 0 關(guān)注
  • 1465 瀏覽
慕課專欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

 公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)