Python的 - 完全數搜索的優化

p = [] 
for x in range(1, 50000000): 
    count = 0 
    for y in range(1, x // 2 + 1): 
     if (x % y == 0): 
      count += y 
    if (count == x): 
     p.append(x)

這是我的代碼，試圖找到一切源於1和5000萬之間，它工作正常的前3個數字完美的數字，它們是1和10000但作爲之間它進展得非常緩慢。比如每10秒鐘可能會有1000個數字。然後最終每5秒鐘通過10個數字。Python的 - 完全數搜索的優化

現在有無論如何我可以做得更快？我嘗試了包括一些較小的東西，比如潛水2 x以確保我們不會超過一半（不會是x的倍數）

來源

2016-11-16 Reece

我認爲你不應該用蠻力的方式來解決這個問題，我建議你閱讀更多關於梅森素數的知識，然後你就會明白你的方法根本不方便:) – BPL

您可以做得更好。考慮以下內容：

1）考慮36的因子分解，例如：1x36,2x18,3x12,4x9,6x6。就是這樣。進一步不會添加任何新東西。下一個因子分解將是9x4，但我們已經知道（4x9）。這個優勢越來越大（比較你必須檢查的最後一個數字的一半與其一半）

2）沒有奇數的完美數字。這實際上是一個猜想（尚未證實），但他們嘗試了10^300以下的所有東西，但沒有找到任何東西。所以肯定沒有任何一個< 50000000.這意味着你可以跳過一半的條款。

from math import ceil 
p = [] 
for x in range(2, 50000000, 2): 
    divisors = {1} 
    for y in range(2, ceil(x**0.5) + 1): 
     if x % y == 0: 
      divisors.update({y, (x//y)}) 
    if sum(divisors) == x: 
     print('-', x) 
     p.append(x) 
#- 6 
#- 28 
#- 496 
#- 8128

這應該是快了很多，但也有肯定更多的事情可以做。

來源

2016-11-16 10:56:28

如果你可以跳過奇數，也可以利用歐幾里德 - 歐拉定理，並計算2 ^（k-1）·（2^k-1）'。 – spectras

我會，但我正在吃午飯！感謝您提醒我！ –

事實上，正如@spectras所示，這是一個很好的解決方案來解決這個問題 – BPL

這是一個使用的Mersenne Primes一些預先計算值的解決方案：

mersenne_prime_powers = [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127] 

def perfect_numbers(n=10): 
    return [(2**p - 1) * (2**(p - 1)) for p in mersenne_prime_powers[:n]] 

print(perfect_numbers(n=5))

輸出：

[6, 28, 496, 8128, 33550336]

來源

2016-11-16 11:12:49 BPL

這裏有一個更簡單的說法，它的含義與此相似：'return [6，28，496，8128，33550336]'。 –

@StefanPochmann從評論「你完全不理解我的答案......」中可以清楚地看出，一個線索是，分析「Mersenne Primes generation」的複雜性，然後回顧OP的原始算法:)。此外，我建議你看看「今日數字」[這裏]（http://www.mersenne.org/），這是非常多的;） – BPL

我認爲這是你誰不明白。我的觀點是，如果你要查找並使用一些你自己無法想出的東西，那麼不妨查看一下你之後的東西。你看我沒有什麼好處。 –

正如已經提到的，沒有奇完全數已被發現。並根據Wikipedia article on perfect numbers，如果存在任何奇數的完美數字，他們必須大於10 。顯然，尋找奇數完美數字需要時間的複雜方法& /或批次。 :)

正如Wikipedia所述，歐幾里德證明即使是完美的數字也可以從梅森素數中產生，而歐拉證明了，相反，所有甚至完美的數字都具有這種形式。

因此，我們可以通過生成梅森素數來生成一個完美數字的列表。我們可以通過Lucas-Lehmer test（相對）快速測試一個數是否是Mersenne素數。

這是一個簡短的程序，可以做到這一點。這裏使用的primes函數是由Robert William Hanks編寫的，其餘的代碼是幾分鐘前我寫的。 :)

''' Mersenne primes and perfect numbers ''' 

def primes(n): 
    """ Return a list of primes < n """ 
    # From http://stackoverflow.com/a/3035188/4014959 
    sieve = [True] * (n//2) 
    for i in range(3, int(n**0.5) + 1, 2): 
     if sieve[i//2]: 
      sieve[i*i//2::i] = [False] * ((n - i*i - 1) // (2*i) + 1) 
    return [2] + [2*i + 1 for i in range(1, n//2) if sieve[i]] 

def lucas_lehmer(p): 
    ''' The Lucas-Lehmer primality test for Mersenne primes. 
     See https://en.wikipedia.org/wiki/Mersenne_prime#Searching_for_Mersenne_primes 
    ''' 
    m = (1 << p) - 1 
    s = 4 
    for i in range(p - 2): 
     s = (s * s - 2) % m 
    return s == 0 and m or 0 

#Lucas-Lehmer doesn't work on 2 because it's even, so we just print it manually :) 
print('1 2\n3\n6\n') 
count = 1 
for p in primes(1280): 
    m = lucas_lehmer(p) 
    if m: 
     count += 1 
     n = m << (p - 1) 
     print(count, p) 
     print(m) 
     print(n, '\n')

輸出

1 2 
3 
6 

2 3 
7 
28 

3 5 
31 
496 

4 7 
127 
8128 

5 13 
8191 
33550336 

6 17 
131071 
8589869056 

7 19 
524287 
137438691328 

8 31 
2147483647 
2305843008139952128 

9 61 
2305843009213693951 
2658455991569831744654692615953842176 

10 89 
618970019642690137449562111 
191561942608236107294793378084303638130997321548169216 

11 107 
162259276829213363391578010288127 
13164036458569648337239753460458722910223472318386943117783728128 

12 127 
170141183460469231731687303715884105727 
14474011154664524427946373126085988481573677491474835889066354349131199152128 

13 521 
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 
23562723457267347065789548996709904988477547858392600710143027597506337283178622239730365539602600561360255566462503270175052892578043215543382498428777152427010394496918664028644534128033831439790236838624033171435922356643219703101720713163527487298747400647801939587165936401087419375649057918549492160555646976 

14 607 
531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127 
141053783706712069063207958086063189881486743514715667838838675999954867742652380114104193329037690251561950568709829327164087724366370087116731268159313652487450652439805877296207297446723295166658228846926807786652870188920867879451478364569313922060370695064736073572378695176473055266826253284886383715072974324463835300053138429460296575143368065570759537328128 

15 1279 
10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087 
54162526284365847412654465374391316140856490539031695784603920818387206994158534859198999921056719921919057390080263646159280013827605439746262788903057303445505827028395139475207769044924431494861729435113126280837904930462740681717960465867348720992572190569465545299629919823431031092624244463547789635441481391719816441605586788092147886677321398756661624714551726964302217554281784254817319611951659855553573937788923405146222324506715979193757372820860878214322052227584537552897476256179395176624426314480313446935085203657584798247536021172880403783048602873621259313789994900336673941503747224966984028240806042108690077670395259231894666273615212775603535764707952250173858305171028603021234896647851363949928904973292145107505979911456221519899345764984291328

即輸出是4.5秒產生的2GHz的32位機器上。你可以很容易地生產更大的梅森素數和完美的數字，但不要指望它快。

來源

2016-11-16 12:05:10

Python的 - 完全數搜索的優化

回答

相關問題