Project Euler 第27题 Python

Question

Project Euler 的第27题是这样的：

欧拉发现了一个很特别的二次公式：

n² + n + 41

这个公式在 n 从 0 到 39 的连续值中会产生 40 个质数。但是，当 n = 40 时，计算 40² + 40 + 41 = 40(40 + 1) + 41 可以被 41 整除，显然当 n = 41 时，41² + 41 + 41 也能被 41 整除。

还有一个很厉害的公式 n² − 79n + 1601 被发现，它在 n 从 0 到 79 的连续值中会产生 80 个质数。这个公式的系数 -79 和 1601 的乘积是 -126479。

现在考虑这样的二次方程：

n² + an + b，其中 |a| < 1000 和 |b| < 1000

这里的 |n| 是 n 的绝对值，比如 |11| = 11 和 |−4| = 4。请找出能产生最多质数的二次表达式的系数 a 和 b 的乘积，要求从 n = 0 开始计算。

这是我的解决方案：

from math import sqrt, fabs

def eSieve(rnge):
    rootedrange = int(sqrt(rnge))
    mydict = dict([(_, True) for _ in range(2, rootedrange)])
    for i in range(2, rootedrange):
        if mydict[i] == True:
            for j in range(i**2, rnge, i):
                mydict[j] = False
    mylist = []
    for key in mydict.keys():
        if mydict[key] is True:
            mylist.append(key)
    return mylist

primes = eSieve(87400)

def isPrime(n):
    i = 0
    while primes[i] <= n:
        if primes[i] == n: return True
        i+=1
    return False

arange = 0
brange = 0
nrange = 0
for a in range(-1000, 1001):
    for b in range(-1000, 1001):
        n = 0
        formula = n*n + a*n + b
        print(formula)
        while(isPrime(fabs(formula))):
            n+=1

        if n > nrange:
            arange = a
            brange = b
            crange = c

print(arange * brange)

我不知道为什么我的程序一直报这个错误：

Traceback (most recent call last):
  File "D:\Programming\ProjectEuler\p27.py", line 33, in <module>
    while(isPrime(fabs(formula))):
  File "D:\Programming\ProjectEuler\p27.py", line 20, in isPrime
    while primes[i] <= n:
IndexError: list index out of range

有没有人能告诉我我的程序在哪里以及如何超出了列表的范围？这真的很不正常。为什么会这样？

Answer 1

如果 isPrime(n) 这个函数需要判断 n 是否在之前创建的素数列表 primes 中，那么你可以很简单地写出这个函数：

def isPrime(n):
    return n in primes

（你的解决方案有问题，因为你的素数列表对 n = 1000 来说太短了。最大的素数是 293，所以 while 条件总是成立。但是过一会儿你想要比较 primes[62] 和 n，这就超出了范围。）

Answer 2

让我们看看如果你想检查1000000是不是一个质数，会发生什么：

i = 0
while primes[i] <= n:
    if primes[i] == n: return True
    i+=1

return False

没有一个被筛选出来的质数大于1000000，所以你的while条件永远不会满足。Python的第一条规则就是不要使用while循环（除非你没有其他循环可以用）。在这里，你可以很容易地用for来替代：

for i in primes:
    if i == n:
        return True

return False

但这正是in操作符要替代的内容：

return n in primes

另外，对于你的isPrime函数，重新实现Python的核心功能n in primes时，item in list在项目数量增加时会比item in set慢。

所以为了写出最快的代码并且减少输入，你可以这样做：

>>> primes = eSieve(87400)
>>> prime_set = set(primes)
>>> 13 in prime_set
True
>>> # or if you want a function:
>>> is_prime = prime_set.__contains__
>>> is_prime(13)
True

__contains__这个神奇的方法可以让set直接返回给定值是否在这个set中——直接使用它比把in操作符放在一个函数里要快得多。