1

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

4

5 回答 5

2

问题出在你的线上

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

于 2013-06-18T12:11:37.897 回答
0

我想说你需要在这里改变方法。您需要符合 1 分钟规则的解决方案。在这里讨论解决方案违背了 Project Euler 的目的。所以我建议你想一个不同的方法来解决这个问题。一种可能在一秒钟内解决问题的方法。

至于内存问题，以目前的方法，几乎​​不可能摆脱它。所以改变方法也将解决这个问题。虽然这篇文章没有回答你的问题，但它符合 Project Euler 的原则！

于 2013-06-18T12:57:34.333 回答
0

检查应该在内部循环之外才能正确终止。否则，程序将永远不会在预期退出时停止。

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，而不是像这样的蛮力方法。

编辑：一种不使用内存的变体。

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
于 2013-06-18T12:22:02.007 回答
0

由于以下大小而发生内存错误：

possible = dict()

一个你不断将整数推入其中，它的大小不断增长，你会得到内存错误。仔细查看解决方案中是否可以避免这种情况。例如。如果答案只需要告诉因素的数量，而不是所有因素，那么不要将所有值存储在列表中并计算其长度。而是为每个数字增加计数器。我不确定问题是什么，但这可以替换为：

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

可 ：

if i in possible:
            possible[i] += 1
        else:
            possible[i] = 0   
if possible[i] == 20:
                print i
                break
于 2013-06-18T12:11:36.520 回答
0

信封计算的快速回溯。你有类似100000000整数的东西，如果你把它们全部存储起来，它们的大小将是 0.4 Gb（在 C 中）。当然，这些是 python 整数，所以每个整数都超过 4 个字节......在我的系统上，每个都是 24（！）字节，这将你的 0.4 Gb 提升到 2.34 Gb。现在您将每个列表存储在最多 21 个列表中……所以（最多）每个列表都有额外的 21 个指针。假设一个指向 int 的 4 字节指针，您可以看到我们已经开始消耗大量内存。

另请注意，出于性能原因，列表被过度分配。您使用的内存可能比您需要的多，因为您的列表未满。

当然，您实际上并没有将它们全部存储起来，而且您有一个（显然）没有受到影响的早期中断条件。您可能在某处有逻辑错误。

于 2013-06-18T12:11:58.350 回答