Project Euler #27: Is there a more optimal way to solve this problem?

Question

I am doing the Quadratic Primes question. My solution is pretty much just loop through every possible option and return the best.

I know that nested loops are not optimal and there's probably a smarter way to find the answer. But I can't think of one that isn't brute force. Here's my code:

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());

Thanks!

Answer 1

Although the algorithm runs very quickly even in JavaScript, there is some area for optimization.

Take a look at the formula: x = n² + an + b.

n will be odd (1, 3, 5, ...) and even (2, 4, 6, ...). Our goal is to make sure that x is always odd, because no even integer other than 2 is prime.

Reminder of rules

odd * odd = odd (3 * 7 = 21)

odd * even = even (3 * 6 = 18)

even * even = even (4 * 8 = 32)

odd + odd = even (3 + 7 = 10)

odd + even = odd (3 + 6 = 9)

even + even = even (4 + 6 = 10)

n²

If n is odd, n squared will be also odd: 1² = 1, 3² = 9, 5² = 25, ...

If n is even, n squared will be also even: 2² = 4, 4² = 8, 6² = 36, ...

So we have alternating odd and even values.

a*n

If a is odd, then:

• for odd n, a*n is odd
• for even n, a*n is even
• so we again have alternating odd and even values.

If a is even, then a*n is always even.

n² + a*n

So far, we have n² + an, which:

• for odd a is equal to odd + odd = even or even + even = even; so it's always even
• for even a is equal to odd + even = odd or even + even = even; so it's alternating odd and even

b

There is just one coefficient left - b. It is a constant, which added to the previous value should yield odd values.

That means we have to ignore even a, because a constant added to alternating odd and even values will also give alternating values, so the formula x will fail after just a few steps.

Since a must be odd, n + an is even.

Therefore, to make x odd, we must take an odd b: even + odd = odd.

Summary

We have to focus only on odd a and odd b values, which will limit the number of cases to check by roughly 4 (= 2 * 2).