我正在嘗試創(chuàng)建一個腳本來為我在Project Euler上解決問題，但是它一直返回MemoryError。我完全不知道為什么。divisible = Truepossible = dict()for i in xrange(1, 100000000): for n in xrange(1, 21): if i%n != 0: divisible = False else: if i in possible: possible[i].append(n) else: possible[i] = [n] if len(possible[i]) == 20: print i breakPython似乎認(rèn)為它發(fā)生在這條線上 possible[i] = [n]
3 回答
繁花不似錦
TA貢獻(xiàn)1851條經(jīng)驗 獲得超4個贊
問題出在你的線上
if len(possible[i]) == 20:
你的意思是說
if len(possible) == 20:
照原樣，您的代碼將繼續(xù)運行-大概是因為循環(huán)計數(shù)如此之大，所以某些堆棧已填滿...
另外-盡管我不確定您要實現(xiàn)的目標(biāo)，但是您的break命令位于最內(nèi)層的循環(huán)中-因此您會中斷該循環(huán)，然后再次執(zhí)行此操作...并且由于長度僅恰好是20一次，因此您仍然被卡住。檢查您的邏輯。
例如，對代碼進(jìn)行以下小的更改將產(chǎn)生有用的輸出（盡管我不知道它是否對您有用...但是它可能會給您一些想法）：
divisible = True
possible = dict()
for i in xrange(1, 100000000):
for n in xrange(1, 21):
if i%n != 0:
divisible = False
else:
if i in possible:
possible[i].append(n)
else:
possible[i] = [n]
if len(possible) == 20:
print i
break
else:
print i, possible[i]
輸出：
1 [1]
2 [1, 2]
3 [1, 3]
4 [1, 2, 4]
5 [1, 5]
6 [1, 2, 3, 6]
7 [1, 7]
8 [1, 2, 4, 8]
9 [1, 3, 9]
10 [1, 2, 5, 10]
11 [1, 11]
12 [1, 2, 3, 4, 6, 12]
13 [1, 13]
14 [1, 2, 7, 14]
15 [1, 3, 5, 15]
16 [1, 2, 4, 8, 16]
17 [1, 17]
18 [1, 2, 3, 6, 9, 18]
19 [1, 19]
20
編輯代碼時要更仔細(xì)，我想您想做的是找到正好有20個因數(shù)的數(shù)字。因此你的情況是正確的。問題在于您還存儲了所有其他術(shù)語-這是非常大量的列表。如果您只在最后一個數(shù)字之后（畢竟唯一的輸出i就在休息之前），那么您真的不需要保留所有其他術(shù)語。下面的代碼就是這樣做的-它在我的計算機(jī)上運行良好，現(xiàn)在占用了最長的時間約20 MB的內(nèi)存（但目前還沒有答案...）
divisible = True
possible = [];
biggest = 0;
bigN = 100000000;
for i in xrange(1, bigN):
for n in xrange(1, 21):
if i%n != 0:
divisible = False
else:
if len(possible) > 0:
possible.append(n)
else:
possible = [n]
if len(possible) >= 20:
print i
print possible
break
else:
if bigN < 1000:
print i, possible; # handy for debugging
if biggest < len(possible):
biggest = len(possible);
possible = []
計算您正在做的事情的“手動”方法是找到所有1到20的數(shù)字的素數(shù)；計算每個中出現(xiàn)質(zhì)數(shù)的最大次數(shù)；并拿走他們的產(chǎn)品：
2 = 2
3 = 3
4 = 22
5 = 5
6 = 2 3
7 = 7
8 = 222
9 = 33
10 = 2 5
11 = 11
12 = 22 3
13 = 13
14 = 2 7
15 = 3 5
16 = 2222
17 = 17
18 = 2 33
19 = 19
20 = 22 5
答案：（2 * 2 * 2 * 2）*（3 * 3）* 5 * 7 * 11 * 13 * 17 * 19 = 232792560
紅顏莎娜
TA貢獻(xiàn)1842條經(jīng)驗 獲得超13個贊
該檢查應(yīng)在內(nèi)部循環(huán)之外，以使其正確終止。否則，程序?qū)⒂肋h(yuǎn)不會在預(yù)期的出口處停止。
divisible = True
possible = dict()
for i in xrange(1, 100000000):
for n in xrange(1, 21):
if i%n != 0:
divisible = False
else:
if i in possible:
possible[i].append(n)
else:
possible[i] = [n]
if len(possible[i]) == 20:
print i
break
順便說一句，一種快速的方法是找到LCM，而不是像這樣的暴力破解方法。
編輯：一種不使用內(nèi)存的變體。
divisible = True
possible = []
for i in xrange(0, 1000000000):
count = 0
for n in xrange(1, 21):
if i%n != 0:
divisible = False
else:
count += 1
if count == 20:
possible.append(i)
print i
else:
print "\r", "%09d %d %d" % (i, 232792560, count),
print possible
達(dá)令說
TA貢獻(xiàn)1821條經(jīng)驗 獲得超6個贊
快速了解封套計算。您有一些類似100000000整數(shù)的東西，如果將它們?nèi)看鎯ζ饋恚瑒t將是0.4 Gb（以C為單位）的數(shù)量級。當(dāng)然，這些是python整數(shù)，因此每個整數(shù)都超過4個字節(jié)...在我的系統(tǒng)上，每個都是24（?。┳止?jié)，這將使0.4 Gb增大為2.34 Gb?，F(xiàn)在，您將每個指針存儲在多達(dá)21個列表中。因此（最多）還有指向每個指針的21個指針。假設(shè)一個指向int的4byte指針，您可以看到我們已經(jīng)開始消耗大量的內(nèi)存。
另請注意，出于性能原因，列表被過度分配。您使用的內(nèi)存可能比您需要的更多，這是因為您的列表不完整。
當(dāng)然，您實際上并沒有全部存儲它們，并且您有一個早期中斷條件（顯然）沒有受到打擊。您的某處可能存在邏輯錯誤。
添加回答
舉報
0/150
提交
取消