Question 242577 in Javascript Question posted in
A very good W3school tutorial can be found here.

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

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

Tags:

3

Answers


  1. 0

    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));
    Login or Signup to reply.
  2. 0

    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))
    Login or Signup to reply.
  3. 0

    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.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search