-1

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!

Jerome
  • 734
  • 1
  • 8
  • 28
  • 2
    I have some generic comments: (1) I'm not sure how about your prime checking algorithms, but usually it's enough to check `i` until `sqrt(num)`. (2) You can use a hash table with all checked prime numbers to avoid re-checking the same numbers again; (3) `|a| < 1000` means `a` is from -999 to 999, and `|b| <= 1000` means `b` is from -1000 to 1000. Your loops are a bit wrong, they should be `i=-999; i < 1000` and `j=-1000; j <= 1000`. – Łukasz Nojek Jul 10 '19 at 06:14
  • 1
    Okay cool! thanks for the feedback. 1. I thought I was doing that with the loop ending that i * i <= num. But I can update it if you think it's faster. 2. Okay, great idea, that will speed it up a bit. 3. Okay, I'll update it now. Thanks @ŁukaszNojek – Jerome Jul 10 '19 at 06:36
  • To be honest, I am not aware of the prime check algorithm you wrote, so I'm not sure if the restriction in (1) will be correct. Have you invented it by yourself or found somewhere? – Łukasz Nojek Jul 10 '19 at 07:45
  • I found it here: https://stackoverflow.com/q/40200089/7918809 – Jerome Jul 10 '19 at 08:13
  • 1
    For the prime optimization: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes – akiva Feb 14 '21 at 05:05

1 Answers1

1

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

Take a look at the formula: x = n2 + 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)

n2

If n is odd, n squared will be also odd: 12 = 1, 32 = 9, 52 = 25, ...

If n is even, n squared will be also even: 22 = 4, 42 = 8, 62 = 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.

n2 + a*n

So far, we have n2 + 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).

Łukasz Nojek
  • 1,511
  • 11
  • 17
  • 1
    if `a` and `n` both are even and `b` is odd, still `x` will be odd, `even + even + odd`, so why `a` must be odd? – AZ_ Jul 10 '19 at 09:23
  • 1
    Because you want to test for `n` from `1` upwards: `1, 2, 3, 4, ...`, so `n` will be once *odd* and the other time *even*. This will change the parity of `x` as `n` changes. And once you get `x` that is *even* and bigger than `2` - it won't be a prime. Therefore that for *even* `a` you will get low scores. – Łukasz Nojek Jul 10 '19 at 09:26