Python代码冻结了我的电脑 - 项目欧拉58

Question

我想通过解决项目欧拉问题来学习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%? 

这是我写的解决此问题的代码。我利用primesieve来检查素数，但我不知道设置primesieve的限制。所以我让代码告诉我什么时候需要增加限制。代码运行良好，限制为10^8，但是当我将其设置为10^9时，代码冻结了我的PC，我必须重新启动。不知道我做错了什么。如果您需要更多信息，请告诉我。谢谢！

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

即使您正在使用的xrange，你还在生成尺寸为10 ** 9的使您的primesieve时的列表。这使用了大量的内存，可能是你的问题。

相反，您可能会考虑通过检查（2，N **。5）之间的任意数字来均等地划分数字来编写一个函数来检查数字N是否为素数。然后，您可以开始生成角点数字并执行素数测试。

Answer 2

这里有一些东西，你可以做，使您的首要发电机更有效率：

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 RAM）。我的CPU只有2.something GHz，并且迄今为止花费了7分钟的时间，作为最高质数的10**8。

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