c++ - 欧拉问题 27

Question

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive

values n = 0 to 39. However, when n = 40, 40^(2) + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula n² − 79n + 1601 was

discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

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.

这是 Euler 27 的问题.

我尝试了一个解决方案来尝试找到方程式 n^2 + n + 41 以查看我的逻辑是否正确，然后我将尝试查看它是否适用于实际问题。这是我的代码(我也会放置注释来解释整个程序，我会先从 int main 函数开始阅读)只需确保阅读注释以便您理解我的逻辑:

#include <iostream>
using namespace std;

bool isPrime(int c) {
    int test;
    //Eliminate with some simple primes to start off with to increase speed...
    if (c == 2) {
        return true;
    }
    if (c == 3) { 
        return true;
    }
    if (c == 5) { 
        return true;
    }
    //Actual elimination starts here.
    if (c <= 1 || c % 2 == 0 || c % 3 == 0 || c % 5 == 0) {
        return false;
    }
    //Then using brute force test if c is divisible by anything lower than it except 1
    //only if it gets past the first round of elimination, and if it doesn't
    //pass this round return false.
    for (test = c; test > 1; test--) {
        if (c % test == 0) {
            return false;
        }
    }
    //If the c pasts all these tests it should be prime, therefore return true.
    return true;
}

int main (int argc, char * const argv[]) {
    //a as in n^2 + "a"n + b
    int a = 0;
    //b as in n^2 + an + "b"
    int b = 0;
    //n as in "n"^2 + a"n" + b
    int n = 0;
    //this will hold the result of n^2 + an + b so if n = 1 a = 1
    //and b = 1 then c = 1^2 + 1(1) + 1 = 3
    int c = 0;
    //bestChain: This is to keep track for the longest chain of primes 
    //in a row found.
    int bestChain = 0;
    //chain: the current amount of primes in a row.
    int chain = 0;
    //bestAB: Will hold the value for the two numbers a and b that
    // give the most consecutive primes.
    int bestAB[2] = { 0 };
    //Check every value of a in this loop
    for (a = 0; a < 40; a++) {
        //Check every value of b in this loop.
        for (b = 0; b < 42; b++) {
            //Give c a starting value
            c = n*n + a*n + b;
            //(1)Check if it is prime. And keep checking until it is not
            //and keep incrementing n and the chain. (2)If it not prime then che
            //ck if chain is the highest chain and assign the bestChain
            // to the current chain. (3)Either way reset the values
            // of n and chain.
            //(1)
            while (isPrime(c) == true) {
                n++;
                c = n*n + a*n + b;
                chain++;
            }
            //(2)
            if (bestChain < chain) {
                bestChain = chain;
                bestAB[0] = a;
                bestAB[1] = b;
                chain = 0;
                n = 0;
            }
            //(3)
            else {
                n = 0;
                chain = 0;
            }
        }
    }
    //Lastly print out the best values of a and b.
    cout << bestAB[0] << " " << bestAB[1]; 
    return 0;
}

但是，我分别得到 a 和 b 的结果 0 和 2，为什么会这样？我哪里错了？如果仍然不清楚，只需要求对特定区域进行更多说明。

Answer 1

您的 isprime 方法效率低下——但也是错误的:

for (test = c; test > 1; test--) {
    if (c % test == 0) {
        return false;
    }
}

在 for 循环的第一次迭代中，test = c，所以 c % test 就是 c % c，它将始终为 0。因此您的 isprime 方法声称所有内容都是非素数(2、3、5 除外)