Prime reversion algorithm - JavaScript

Question

I solved the following problem:

Consider the range 0 to 10. The primes in this range are: 2, 3, 5, 7, and thus the prime pairs are: (2,2), (2,3), (2,5), (2,7), (3,3), (3,5), (3,7),(5,5), (5,7), (7,7).

Let's take one pair (2,7) as an example and get the product, then sum the digits of the result as follows: 2 * 7 = 14, and 1 + 4 = 5. We see that 5 is a prime number. Similarly, for the pair (7,7), we get: 7 * 7 = 49, and 4 + 9 = 13, which is a prime number.

You will be given a range and your task is to return the number of pairs that revert to prime as shown above. In the range (0,10), there are only 4 prime pairs that end up being primes in a similar way: (2,7), (3,7), (5,5), (7,7). Therefore, solve(0,10) = 4)

Note that the upperbound of the range will not exceed 10000. A range of (0,10) means that: 0 <= n < 10.

I was wondering if my solution could be improved or if I should use a completely different approach.

function isPrime(n) {
    if(n < 2){
        return false;
    }
    for (var i = 2; i <= parseInt(Math.sqrt(n)); i++) {
        if (n % i === 0) {
            return false;
        }
    }
    return true;
}

function getPrimes(s, e) {
    var primes = [];
    for (var p = s; p <= e; p++) {
        if(isPrime(p)){
            primes.push(p);
        }
    }
    return primes;
}

function generatePairs(primes){
    var pairs = [];
    for(var i = 0; i < primes.length; i++){
        for(var j = i; j < primes.length; j++){
            pairs.push([primes[i], primes[j]]);
        }
    }
    return pairs;
}

function sumDigits(n){
    var sum = 0;
    while(n > 0){
        sum += n % 10;
        n = parseInt(n/10);
    }
    return sum;
}

function solve(a, b) {
    var pairs = generatePairs(getPrimes(a, b - 1));
    var res = 0;
    for(pair of pairs){
        var tmp = sumDigits(pair[0] * pair[1]);
        if(isPrime(tmp)){
            res++;
        }

    }
    return res;
}

Answer 1

Your code looks good, just a few small things I would change. First, I didn't know where to start reading your code, since the function you would start with is at the bottom, and your example doesn't actually call it.

parseInt is used to convert a string to a number. If you just want to floor a number, use Math.floor instead. It is much faster.

In the isPrime function, every iteration of the loop calculates the same square root, which is not a simple calculation. Store the square root in a variable before the loop, and compare to that.

The getPrimes function works fine, but has potential for optimization, based on what we know about primes. For instance, with exception of 2, every primes is odd, so you only need to check every second number. You could also look into other methods, like a prime sieve.

There is no reason to still is var. Use let and const.