Python 大循环发生内存错误

Question

我正在尝试创建一个脚本来解决我在 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]

Answer 1

问题出在你的线路上

if len(possible[i]) == 20:

你的意思是

if len(possible) == 20:

事实上，您的代码将继续运行 - 并且可能，由于循环计数太大，一些堆栈已填满......

另外 - 虽然我不确定你想要实现什么目标，但你的 break 命令位于最内层循环 - 所以你打破它，然后再次循环......由于长度只会正好是 20 一次，所以你仍然被卡住了。检查你的逻辑。

例如，对代码进行以下小更改会产生有用的输出(虽然我不知道它对您是否有用......但它可能会给您一些想法):

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

编辑仔细阅读代码，我认为您想要做的是找到正好有 20 个因数的数字；因此你的情况是正确的。问题是您还存储了所有其他术语 - 这是一个非常非常大的列表。如果您仅在最后一个数字之后(毕竟唯一的输出是在休息之前的 i )，那么您确实不需要保留所有其他项。下面的代码就是这样做的 - 它在我的计算机上运行得很好，目前占用了大约 20 MB 的内存(但还没有答案......)

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 的所有数字的质因数；计算每个素数出现的最大次数；并采取他们的产品:

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