027. 二次质数(Quadratic primes)

欧拉发现了著名的二次公式：\(n^2+n+41\)，发现这个公式可以对于\(0\leq n \leq39\)的整数可以连续产生四十个素数。然而，当\(n=40,40^2+40+41=40(40+1)+41\)可以被\(41\)整除；当\(n=41,41^2+41+41\)显然也可以被\(41\)整除。

另外一个著名公式是\(n^2-79n+1601\)，可以对\(0\leq n \leq79\)的整数连续产生80个素数，这个议程两个系数\(-79\)和\(1601\)的乘积是\(-126479\)。

考虑如下二次公式：

$$ n^2+an+b,where\ |a|<1000 \ and\ |b|<1000 $$

求使得以上公式从\(n=0\)开始连续产生的素数最多的系数\(a\)与\(b\)的乘积。

分析：首先，我们可以分析一下系数\(a\)与\(b\)需要满足的性质。假设\(n=0\)，\(f(0)=0^2+0+b=b\)必须是一个素数，也就是说\(b\)必须是一个素数；假设\(n=1\)，则\(f(1)=1+a+b\)必须是一个素数，我们已经知道\(b\)必须是一个素数，又因为除2以外所有素数都是奇数，则在\(b\ne2\)时，则\(a\)必须是一个奇数。如果\(b=2\)，取\(n=2\)，则\(f(2)=2^2+2a+2=2(a+3)\)为偶数则必不为素数，则\(n\)的取值只能是0和1，此公式最多只能产生两个素数，肯定不是产生素数最多的公式，所以可以把\(b=2\)的情况排除。综上所述，\(b\)为除二以外的素数，\(a\)为奇数，这样我们大幅度缩小筛选系数的范围。

在确定了筛选的系数范围后，只需要对每一对系数求其产生的素数个数，方法是从\(n=0\)开始依次代入不同的\(n\)，看所产生的数是否为素数。如果是素数，则对\(n\)累加一，再求数值判断是否为素数。如果不是素数则跳出循环，得到的\(n\)的值即这个公式可以产生的素数个数。然后我们对系数范围内的值形成的公式依次求它们可以产生的素数个数并存储相应的字典中，字典的键为系数对可以产生的素数个数，值为相应的系数对，最后我们求最大的键对应的系数对的乘积，即为所求。

from sympy import isprime

def primes_number(a,b):
    f = lambda n,a,b : n**2 + a*n + b
    n = 0
    while True:
        if isprime(f(n,a,b)):
            n = n + 1
        else:
            return n

def main():
    res = {}
    for a in range(-999,1000,2):
        for b in [x for x in range(-1000,1001) if isprime(x)]:
            res[primes_number(a,b)] = (a,b)
    a,b = res[max(res)]
    return a*b