Problem 27 Quadratic primes

2016-10-10 12:05:00   技术   projecteulor python

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)

感想:

  1. 暴力破解很无耻
  2. 该break时候就应该break
评论已关闭。
评论共