欧拉计划#27:有没有更优化的方法来解决这个问题?

Question

我正在做二次素数问题。我的解决方案几乎只是遍历每个可能的选项并返回最好的。

我知道嵌套循环不是最佳的，可能有更聪明的方法可以找到答案。但我想不出一个不是蛮力的。这是我的代码：

var isPrime = function(num) {
if (num <= 1) {
return false;
}
// The check for the number 2 and 3
if (num <= 3) {
return true; 
}
if (num % 2 == 0 || num % 3 == 0) {
return false;
}
for (var i = 5; i * i <= num; i = i + 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
var main = function () {
var max = 0;
var a = 0;
var b = 0;
for (var i = -999; i < 1000; i++) {
for (var j = -1000; j <= 1000; j++) {
var n = 0;
while(1) {
var temp = Math.pow(n, 2) + (n * i) + j;
if (isPrime(temp)) {
if (n > max) {
max = n;
a = i;
b = j;
}
} else {
break;
}
n++;
}
}
}
return a * b;
}
console.log(main());

谢谢！

Answer 1

尽管该算法即使在 JavaScript 中也能运行得非常快，但仍有一些需要优化的地方。

看看公式：x = n²+ an + b。

n将是奇数(1,3,5，...)和偶数(2,4,6，...)。我们的目标是确保x总是奇数，因为除了 2 之外，没有偶数是素数。

规则提醒

奇数 * 奇数 = 奇数 (3 * 7 = 21)

奇数 * 偶数 =偶数 (3 * 6 = 18)

偶数 * 偶数 = 偶数 (4 * 8 = 32)

奇数 + 奇数 = 偶数 (3 + 7 = 10)

奇数 + 偶数 = 奇数 (3 + 6 = 9)

偶数 + 偶数 = 偶数 (4 + 6 = 10)

n²

如果n是奇数，n平方也是奇数：1²= 1,3 2 = 9,5²= 25，...

如果n是偶数，则n平方也将是偶数：2²= 4， 4 2 = 8， 6²= 36， ...

所以我们有交替的奇数值和偶数值。

a*n

如果a是奇数，那么：

• 对于奇数n，a*n是奇数
• 对于偶数n，a*n是偶数
• 因此，我们再次具有交替的奇数值和偶数值。

如果a是偶数，那么a*n总是偶数。

n

²+ a*n

到目前为止，我们有n²+ an，它：

对于奇数a等于奇数 + 奇数 = 偶数或偶数 + 偶数 = 偶数

• ;所以它总是偶数
• 因为偶数a等于奇数+ 偶数 = 奇数或偶数 + 偶数 = 偶数;因此它是奇数和偶数交替
的

乙

只剩下一个系数 -b.它是一个常量，添加到前一个值应该产生奇数值。

这意味着我们必须忽略偶数a，因为添加到交替奇偶值的常量也会给出交替值，因此公式x只需几步就会失败。

由于a必须是奇数，因此n + an是偶数。

因此，为了使x奇数，我们必须采取奇数b：偶数+奇数=奇数。

总结

我们只需要关注奇数a和奇数b值，这将限制要检查的案例数量大约 4 (= 2 * 2)。