Euler discovered the remarkable quadratic formula:
\[n^2 + n + 41\]It turns out that the formula will produce 40 primes for the consecutive integer values \(0 \le n \le 39\). However, when \(n = 40, 40^2 + 40 + 41 = 40(40 + 1) + 41\) is divisible by 41, and certainly when \(n = 41, 41^2 + 41 + 41\) is clearly divisible by 41.
The incredible formula \(n^2 - 79n + 1601\) was discovered, which produces 80 primes for the consecutive values \(0 \le n \le 79\). The product of the coefficients, −79 and 1601, is −126479.
Considering quadratics of the form:
\(n^2 + an + b\), where \(|a|< 1000\) and \(|b|\le1000\)
where \(|n|\) is the modulus/absolute value of \(n\)
e.g. \(|11| = 11\) and \(|−4| = 4\)
Find the product of the coefficients, \(a\) and \(b\), for the quadratic expression that produces the maximum number of primes for consecutive values of \(n\), starting with \(n = 0\).
第27题 二次“素数生成”多项式”
欧拉发现了这个著名的二次多项式:
\[n^2 + n + 41\]对于连续的整数n,\(0 \le n \le 39\),这个二次多项式生成了40个素数。然而,当\(n = 40\)时,\(40^2 + 40 + 41 = 40(40 + 1) + 41\)能够被41整除,同时显然当\(n = 41\)时,\(41^2 + 41 + 41\)也能被41整除。
随后,另一个神奇的多项式\(n^2 - 79n + 1601\)被发现了,对于连续的整数n,\(0 \le n \le 79\),它生成了80个素数。这个多项式的系数-79和1601的乘积为-126479。
考虑以下形式的二次多项式:
\(n^2 + an + b\), 满足 \(|a|< 1000\) 且 \(|b|\le1000\)
其中\(|n|\) 指\(n\)的模或绝对值 例如 \(|11| = 11\) 以及 \(|−4| = 4\)
这其中存在某个二次多项式能够对从0开始尽可能多的连续整数\(n\)都生成素数,求其系数a和b的乘积。
import math
def is_Prime(number):
if number < 2:
return False
for x in range(2, int(math.sqrt(number)) + 1):
if number % x == 0:
return False
return True
result_count = 0
result_a = -1000
result_b = -1000
for a in range(-1000, 1000):
for b in range(1, 1000):
count = 0
for x in range(0, 1001):
if is_Prime(x * x + a * x + b):
count += 1
else:
if count > result_count:
result_count = count
result_a = a
result_b = b
print "a = %s, b = %s, count = %s" % (a, b, count)
break
print
print "product = %s" % (result_a * result_b)
感想:
- 暴力破解很无耻
- 该break时候就应该break