Find the next greater prime of a given number

Question

Here's the code i wrote to solve the problem:

let isPrime = function(n) {
    for (let i = 2; i < n; i++) {
        if (n % i === 0) {
            return false;
        }
    }
    
    return true;
};

    
function nextPrime(num) {
    let newNum = num;
    
    for (let i = 0; i < newNum; i++) {
        if (!isPrime(newNum)) {
            newNum += 1;
        } else if (isPrime(newNum)) {
            return newNum;
        }
    }
};

My plan is:

// increment the num by 1 and check if that new num is prime;
// if not, increment again and check again. Repeat the process untill prime is found.

Input and (expected output is commented):

console.log(nextPrime(2)); // 3
console.log(nextPrime(3)); // 5
console.log(nextPrime(7)); // 11
console.log(nextPrime(8)); // 11
console.log(nextPrime(20)); // 23
console.log(nextPrime(97)); // 101

The output i'm getting;

I'd like to know where exactly my implementation is wrong. Also, i'd like the code to be without fancy methods because i'm new to all this. Thank you!

You don't like fancy methods, and you are getting into primes? Oh-oh! — vitaly-t, Nov 08 '22 at 16:05
P.S. Two numbers before the last one are actually from the expected output — Ali, Nov 08 '22 at 16:07
you're only incrementing newNum for the first time after checking if it's prime. — TZHX, Nov 08 '22 at 16:07
[How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) and [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) The problem is that your code checks the current number and if it's prime, it returns it. Instead of checking the next number first. — VLAZ, Nov 08 '22 at 16:07
so a few things wrong here. first in isPrime you start your loop at 2 and loop until i < n. when n is 2 (in your first example) the loop cannot be run and therefore we return true even though 2 is not prime. second, your nextPrime function starts by checking the num that was passed to see if it is prime, so if it is then we are going to return the same number back. you should start your newNum at num+ 1 instead — Portal, Nov 08 '22 at 16:14
@ASDFGerte correct, my mistake. Not to mention that case's problem is fixed entirely by my second point. — Portal, Nov 08 '22 at 16:17
Besides 2, all primes are odd. Better increment by 2. Also, it is a big waste to try all i until n, because if n has a factor that exceeds √n, there is another below √n. Use the stopping criterion i * i < n. — , Nov 08 '22 at 16:23
@YvesDaoust "*Besides 2, all primes are odd. Better increment by 2.*" Then what would you get for `nextPrime(4)`? — VLAZ, Nov 08 '22 at 16:39
@VLAZ: this optimization holds for both `isPrime` and `nextPrime` functions, with appropriate care... — , Nov 08 '22 at 16:56
@VLAZ: After excluding the `2` case, tweak the start point with `| 1` so it's guaranteed odd. Or with `- 1` then `| 1` so initial odds are unchanged and evens back up to the prior odd number or whatever works for your specific design. — ShadowRanger, Nov 11 '22 at 00:52

score 0 · Answer 1 · answered Nov 08 '22 at 16:18

The assignment newNum = num precisely does not make newNum a new number, but the same ! This is why the function returns immediately when the input argument is prime.

By the way, the loop would be much cleaner as

do
{
  newNum += 1;
} while (!isPrime(newNum));

score 0 · Answer 2 · answered Nov 11 '22 at 00:46

function nextPrime(previousPrime) {
    const value = previousPrime;
    if (value > 2) {
        var i, q;
        do {
            i = 3;
            value += 2;
            q = Math.floor(Math.sqrt(value));
            while (i <= q && value % i) {
                i += 2;
            }
        } while (i <= q);
        return value;
    }
    return value === 2 ? 3 : 2;
}

Find the next greater prime of a given number

2 Answers2