Is this a bad way to check prime number using Javascript

Question

const input = 3;
let isPrime = true;
 outer: for(let i = 2; i < input; i++){
        for(let j = 2; j < input; j++) {
         if((i * j) === input) {
                  isPrime = false;
                  console.log(`${input} is Not a prime number`);
                  break outer;
              }
      }
}
if(isPrime) {
    console.log(`${input} is a prime number`); }

Personally, I think this is not the right way, even though I could've done it in an easier way, I approached the problem like so. I needed some feedback from my seniors, can I get a code review?

yeah, it's bad. you can do it in `O(n)` time. you just need to check if any number from 2 to `input/2` can divide input. — nullptr, Sep 18 '22 at 06:45
It's fine it's just incredibly slow =). @nullptr if you are picking a simple limit, you can end on sqrt(input) — Evert, Sep 18 '22 at 06:46
Related question: [Number prime test in JavaScript](https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript) — Yogi, Sep 18 '22 at 06:49
@Evert an even better condition would be `i*i <= sqrt(input)` because `sqrt` is an expensive operation. — nullptr, Sep 18 '22 at 07:31
Questions has answer. Which was not good in term of memory and space. — Deepesh kumar Gupta, Sep 18 '22 at 10:45
[Here's high-performance example](https://github.com/vitaly-t/prime-lib/blob/main/src/is-prime.ts). — vitaly-t, Sep 24 '22 at 02:47

Tunahan Akdogan · Answer 1 · 2022-09-18T09:47:43.733

0

Nested loops are mostly time consuming solutions. If you have an other option you need to probably do that. In this case you using nested for loops to determine prime number. But you can do it with only one for loop.

const number = 3
let isPrime = true;

// check if number is equal to 1
if (number === 1) {
    console.log("1 is neither prime nor composite number.");
}

// check if number is greater than 1
else if (number > 1) {

  
    for (let i = 2; i <= Math.sqrt(number); i++) {
        if (number % i == 0) {
            isPrime = false;
            break;
        }
    }

    if (isPrime) {
        console.log(`${number} is a prime number`);
    } else {
        console.log(`${number} is a not prime number`);
    }
}

For more information you can check these links: Why nested loops are bad practice Finding a prime number

edited Sep 18 '22 at 09:47

answered Sep 18 '22 at 06:55

Tunahan Akdogan

246
2
9

1

(As already pointed out by @Evert in the comments below the question:) You do not need to try all numbers up to `number - 1`. Checking up to the square root is sufficient (so you could abort the loop at `i <= Math.sqrt(number)`). – MartinHH Sep 18 '22 at 07:13
@MartinHH I missed the comments thank you I edited the answer. – Tunahan Akdogan Sep 18 '22 at 09:48
1

Thanks a lot for investing your time for this – Sep 18 '22 at 11:48
1

As nullptr pointed out, if Math.sqrt is slow you can also do `i * i < number` which will be the same but faster. If you do keep Math.sqrt, it's better to do that calculation once outside the loop instead of doing that check for every iteration. – Evert Sep 18 '22 at 19:16
1

Also instead of `i+` you can do `i+2`. Skip the even numbers.. Reduces the checks by half again. You could also skip any number ending in `0` or `5`, but not sure if that extra check is faster or slower. If you need to check *many* numbers for prime, it's best to remember all previous prime numbers and only check against those instead of every number. – Evert Sep 18 '22 at 19:17

Is this a bad way to check prime number using Javascript

1 Answers1