prime number finder doesn't work for certain values in javascript.what did I do wrong?

Question

I'm writing a code that finds prime numbers lesser than n,but the code gives me back 33 and 35 as prime numbers.I don't understand why.Here's my code:

function primeFinder(n) {
  let prime = []
  let index = 0
  for (let i = 2; i <= n; i++) {
    let root = Math.floor(Math.sqrt(i))
    for (let j = 2; j <= root; j++) {
      if (i % j == 0) {
        i++
        break
      }
    }
    prime[index] = i
    index++
  }
  return (prime)
}

console.log(primeFinder(35))

I tried to find the prime numbers but it doesn't work as expected

[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) — VLAZ, Sep 01 '23 at 18:29
FYI, there's no need for the `index` variable. Use `prime.push(i)` to add to an array. — Barmar, Sep 01 '23 at 18:36
your `break` only breaks out of the `j` loop, not the `i` loop. — Pointy, Sep 01 '23 at 18:38
You realize your output contains all odd numbers, not just 33 and 35, right? 9, 15, 21, 25, etc. are all not prime. — user229044, Sep 01 '23 at 18:42
Every ask is important because that i give a upvote, the downvotes are not good for people searching a valid answer — Franz Kurt, Sep 01 '23 at 18:59

score 2 · Answer 1 · answered Sep 01 '23 at 18:44

Your inner loop stops as soon as it finds a divisor of i, which means that i is not prime. Then it increments i and adds this to the prime array. So for every non-prime value, it returns i+1 as the next prime.

You need to detect whether or not you make it all the way through the inner loop without finding a divisor, which means that the number is prime. Set a flag before the loop, update it when you find a divisor, and check the flag afterward.

function primeFinder(n) {
  let prime = [];
  for (let i = 2; i <= n; i++) {
    let root = Math.ceil(Math.sqrt(i))
    let primeFlag = true;
    for (let j = 2; j <= root; j++) {
      if (i % j == 0) {
        primeFlag = false;
        break;
      }
    }
    if (primeFlag) {
      prime.push(i)
    }
  }
  return (prime)
}

console.log(primeFinder(35))

score 1 · Answer 2 · answered Sep 01 '23 at 18:36

1

Try something like this:

function primeFinder(n) {
  const primes = [];

  for (let i = 2; i <= n; i++) {
    let isPrime = true;
    const root = Math.floor(Math.sqrt(i));

    for (let j = 2; j <= root; j++) {
      if (i % j === 0) {
        isPrime = false;
        break;
      }
    }

    if (isPrime) {
      primes.push(i);
    }
  }

  return primes;
}

console.log(primeFinder(35));

answered Sep 01 '23 at 18:36

TropicalTony

31
2

2

lol. same answer, but this would be a bunch better if you explain what the issue is. – Tibrogargan Sep 01 '23 at 18:41
it works now.thanks a lot!!! – yasser fahmi Sep 01 '23 at 18:42
1

When you increment i inside the loop, you're skipping some numbers – TropicalTony Sep 01 '23 at 18:45

Coding Ninja · Answer 3 · 2023-09-01T19:19:53.270

When i is divisible with j, you just break the for statement and didn't ignored adding i to the prime list.

    for (let j = 2; j <= root; j++) {
      if (i % j == 0) {
        i++
        break // This break doesn't affect pushing i into primes
      }
    }
    prime[index] = i // The i is pushed to primes no matter i is divisible by j
    index++

That's why you get all odd numbers as prime.

And for performance, your function will take much time if n is big enough. Here's the optimized code for getting all primes under n.

function primeFinder(n) {
  const primes = [];
  const isPrime = [];
  for (let i = 0; i <= n; i += 1) {
    isPrime[i] = true;
  }
  const root = Math.floor(Math.sqrt(n));
  for (let i = 2; i <= root; i++) {
    if (isPrime[i] == false) continue;
    for (let j = i; j <= n; j += i) {
      isPrime[j] = false;
    }
  }
  for (let i = 2; i <= n; i += 1) {
    if (isPrime[i]) primes.push(i);
  }

  return primes;
}

Remember, division takes much time in all programming languages and you should avoid them as you can. In the code above, we don't do any divisions.

You're avoiding the cost doing division by adding the cost of more memory, and adding the cost of doing initialization, and worst of all adding the cost of having code that doesn't work at all. You don't actually have a test for prime. — Tibrogargan, Sep 01 '23 at 19:15
For big n, using those general methods doesn't make the result in short time. This algorithm is known as 'Sieve of Eratosthenes' and will get better performance when n is so big. And of course I have tested this function, and it works well. You should try, and will get perfect result. — Coding Ninja, Sep 01 '23 at 19:18

prime number finder doesn't work for certain values in javascript.what did I do wrong?

3 Answers3