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。

如果你看看我在評論中鏈接的帖子，有一些更好的方法來生成素數，但這些都是一些簡單的改進。