Python 代码冻结了我的电脑 - Project Euler 58

Question

我正在尝试通过解决 Project 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 时，代码冻结了我的 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，您在制作 primesieve 时仍会生成大小为 10**9 的列表。这会占用大量内存，可能是您的问题。

相反，您可以考虑编写一个函数来检查数字 N 是否为质数，方法是检查 (2,N**.5) 之间的任何数字是否均分。然后，您可以着手生成角编号并执行素性测试。

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% 或更多，万岁！）但几乎不使用任何内存（例如，几 MB RAM x 7分钟）。我的 CPU 只有 2.something GHz，到目前为止 10**8 花了 7 多分钟作为最大质数。

如果您查看我在评论中链接的 post，可以找到一些更好的生成素数的方法，但这些只是一些简单的改进。

Python 代码冻结了我的电脑 - Project Euler 58

Python code freezes up my computer - Project Euler 58

python

performance

processing-efficiency