Project Euler に関する質問を解決するためのスクリプトを作成しようとしていますが、MemoryError が返され続けます。理由はまったくわかりません。
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
Pythonは、この行で発生すると考えているようですpossible[i] = [n]
The problem is in your line
if len(possible[i]) == 20:
You mean to say
if len(possible) == 20:
As it is, your code will keep on running - and presumably, since the the loop count is so large, some stack fills up...
Also - although I don't know for sure what you are trying to achieve, your break command is in the innermost loop - so you break out of it, then go around again... and since the length will only be exactly 20 once, you are still stuck. Check your logic.
for example, the following small change to your code produces useful output (although I don't know if it's useful for you... but it might give you some ideas):
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]
Output:
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
EDIT reading through the code more carefully, I think what you are trying to do is find the number that has exactly 20 factors; thus your condition was correct. The problem is that you are storing all the other terms as well - and that is a very very large number of lists. If you are only after this last number (after all the only output is i just before the break), then you really don't need to keep all the other terms. The following code does just that - it's been running merrily on my computer, taking about 20 MB of memory for the longest time now (but no answer yet...)
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 = []
The "manual" way to calculate what you are doing is finding the prime factors for all numbers from 1 to 20; counting the largest number of times a prime occurs in each; and taking their product:
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
Answer: (2*2*2*2)*(3*3)*5*7*11*13*17*19 = 232792560
ここでアプローチを変更する必要があると思います。1 分ルールに適合するソリューションが必要です。そして、ここで解決策について議論することは、Project Euler の目的そのものを無効にします。そのため、問題を解決するための別のアプローチを考えることをお勧めします。問題を 1 秒もかからずに解決する可能性のあるアプローチ。
メモリの問題に関しては、現在のアプローチでは、それを取り除くことはほとんど不可能です。したがって、アプローチを変更すると、この問題も解決します。この投稿はあなたの質問に答えるものではありませんが、Project Euler の原則に沿ったものです!
The memory error is occuring due to the size of :
possible = dict()
One you keep pushing integers into it, its size keeps on growing, and you get memory error. Carefully see if that can be avoided in the solution.eg. If the answer requires only to tell the count of factors, and not all factors, then do not store all values in a list and calculate its length. Instead increment counters for each number. I am not sure what the question is, but this can be replaced by this :
if len(possible[i]) == 20:
print i
break
can be :
if i in possible:
possible[i] += 1
else:
possible[i] = 0
if possible[i] == 20:
print i
break
エンベロープ計算のクイックバック。整数のようなものが100000000あり、それらをすべて格納すると、(C で) 0.4 Gb 程度になります。もちろん、これらは python 整数なので、それぞれが 4 バイトを超えています... 私のシステムでは、それぞれが 24(!) バイトで、0.4 Gb から 2.34 Gb までかかります。これで、それぞれが最大 21 個のリストに格納されました。つまり、それぞれに (最大で) 21 個のポインターが追加されます。int への 4 バイトのポインターを想定すると、すでに膨大な量のメモリを消費し始めていることがわかります。
また、パフォーマンス上の理由から、リストが過剰に割り当てられていることにも注意してください。リストがいっぱいではないため、必要以上のメモリを使用している可能性があります。
もちろん、実際にはそれらすべてを保存しているわけではなく、(明らかに) ヒットしていない初期のブレーク状態があります。どこかに論理エラーがある可能性があります。
正しく終了するには、チェックがインナーループの外にある必要があります。そうしないと、意図した終了時にプログラムが停止することはありません。
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 を見つけることです。
編集: メモリを使用しない 1 つのバリアント。
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