Python代码冻结了我的计算机项目

Question

我试图通过解决Euler项目中的问题来学习python。我被困在问题58上了。问题是这样的：

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

这是我为解决这个问题写的代码。我使用质数筛检查质数，但我不知道设置质数筛的极限。所以我让代码告诉我什么时候需要增加限制。代码在limit=10^8时运行良好，但当我将其设置为10^9时，代码会冻结我的电脑，我必须重新启动。不知道我做错了什么。如果你需要更多的信息，请告诉我。谢谢！你知道吗

def primesieve(limit):
    primelist=[]
    for i in xrange(limit):
        primelist.append(i)

    primelist[1]=0
    for i in xrange(2,limit):
        if primelist[i]>0:
            ctr=2
            while (primelist[i]*ctr<limit):
                a=primelist[i]*ctr
                primelist[a]=0
                ctr+=1

    primelist=filter(lambda x: x!=0, primelist)
    return primelist

limit=10**7
plist=primesieve(limit)
pset=set(plist)

diagnumbers=5.0
primenumbers=3.0
sidelength=3
lastnumber=9

while (primenumbers/diagnumbers)>=0.1:
    sidelength+=2
    for i in range(3):
        lastnumber+=(sidelength-1)
        if lastnumber in pset:
            primenumbers+=1
    diagnumbers+=4
    lastnumber+=(sidelength-1)
    if lastnumber>plist[-1]:
        print lastnumber,"Need to increase limit"
        break

print "sidelength",sidelength,"  last number",lastnumber,(primenumbers/diagnumbers)

Answer 1

以下是一些可以让主生成器更高效的方法：

def primesieve(limit):
    primelist=[]

    # Don't create a list of all your numbers up front.
    # And even if you do, at least skip the even numbers!
    #for i in xrange(limit):
    #    primelist.append(i)

    # Skip counting - no even number > 3 is prime!
    for i in xrange(3, limit, 2):

        # You only need to check up to the square root of a number:
        # I *thought* that there was some rule that stated that a number
        # was prime if it was not divisible by all primes less than it,
        # but I couldn't find that for certain. That would make this go
        # a lot faster if you only had to check primes and numbers greater
        # than the greatest prime found so far up to the square root of
        # the number
        for divisor in xrange(3, int(i**0.5)+1, 2):
            if not i % divisor:  # no remainder, so sad
                break
        else:
            # loop exited naturally, number has no divisors hooray!
            primelist.append(i)

    # Need to put the number 2 back, though
    primelist.insert(0, 2) 
    return primelist

这使用了混乱我的CPU（100%或更多，万岁！）但几乎不使用任何内存（比如，一个7分钟内存的几MB内存）。我的CPU只有2.5GHz左右，到目前为止，10**8作为最大主处理器已经用了7分钟。你知道吗

如果你看我在评论中链接的帖子，有一些更好的方法来生成素数，但是这些是一些简单的改进。你知道吗

Answer 2

即使您使用的是xrange，但在制作primesieve时仍然会生成一个大小为10**9的列表。这会占用大量内存，很可能是你的问题。你知道吗

相反，您可以考虑编写一个函数，通过检查（2，N**.5）和（2，N**.5）之间的任何数字，来检查一个数N是否为素数。然后，您可以开始生成角点编号，然后执行素性测试。你知道吗