How can I find the prime factors of an integer in JavaScript?

I do believe there is a mistake in both code above. If you replace the integer by 100 the prime factorization won't work anymore as the factor 2 cannot be considered with those for loops. As j = 2, i = 2 and j<=i/2 in the condition - meaning the loop will never run for i=2, which is a prime factor.

Tried to make it work this way but couldn't figure out.

Had to rely on a different approach with a while loop here :

    function getAllFactorsFor(remainder) {
    var factors = [], i;

    for (i = 2; i <= remainder; i++) {
        while ((remainder % i) === 0) {
            factors.push(i);
            remainder /= i;
        }
    }

    return factors;
}

https://jsfiddle.net/JamesOR/RC7SY/

You could also go with something like that :

let findPrimeFactors = (num) => {
    let arr = [];


    for ( var i = 2; i < num; i++) {
        let isPrime
        if (num % i === 0) {
            isPrime = true;
            for (var j = 2; j <= i; j++) {
                if ( i % j === 0) {
                isPrime == false;
                }
            } 
        }if (isPrime == true) { arr.push(i)}

    }console.log(arr)
}

findPrimeFactors(543)

The answer above is inefficient with O(N^2) complexity. Here is a better answer with O(N) complexity.

function primeFactors(n) {
  const factors = [];
  let divisor = 2;

  while (n >= 2) {
    if (n % divisor == 0) {
      factors.push(divisor);
      n = n / divisor;
    } else {
      divisor++;
    }
  }
  return factors;
}

const randomNumber = Math.floor(Math.random() * 10000);
console.log('Prime factors of', randomNumber + ':', primeFactors(randomNumber).join(' '))

You can filter for duplicates as you please!


When factorizing an integer (n) to its prime factors, after finding the first prime factor, the problem in hand is reduced to finding prime factorization of quotient (q).

Suppose n is divisible to prime p1 then we have n = p1 * q1 so after finding p1 the problem is reduced to factorizing q1 (quotient). If the function name is primeFactorizer then we can call it recursively and solution for n would be:

n = p1 * primeFactorizer(q1)

n = p1 * p2 * primeFactorizer(q2)

...

Until qn is prime itself.

Also I'm going to use a helper generator function which generates primes for us:

function * primes () {
  let n = 2
  while (true) {
    let isPrime = true
    for (let i = 2; i <= n / 2; i++) {
      if (n % i === 0) {
        isPrime = false
        break
      }
    }
    if (isPrime) {
      yield n
    }
    n++
  }
}

And function to factorize n would be:

function primeFactorizer (n, result = []) {
  for (const p of primes()) {
    if (n === p) {
      result.push(p)
      return result
    }
    if (n % p === 0) {
      result.push(p)
      return primeFactorizer(n / p, result)
    }
  }
}

Here's a working solution:

function getPrimeFactors(integer) {
  const primeArray = [];
  let isPrime;

  // Find divisors starting with 2
  for (let i = 2; i <= integer; i++) {
    if (integer % i !== 0) continue;

    // Check if the divisor is a prime number
    for (let j = 2; j <= i / 2; j++) {
      isPrime = i % j !== 0;
    }

    if (!isPrime) continue;
    // if the divisor is prime, divide integer with the number and store it in the array
    integer /= i
    primeArray.push(i);
  }

  return primeArray;
}

console.log(getPrimeFactors(13195).join(', '));

You were very much on the right track. There were two minor mistakes. The evaluation of integer - 1 seemed to be incorrect. I believe the more appropriate evaluation is <= integer in your outer for loop. This is because when you divide your integer below integer /= i, this results in the final integer evaluation to be 29. The final prime divisor in this case is also 29 and as such will need to be evaluated as <= as oppose to < integer - 1.

As for why the final log statement isn't working, there was a simple typo of primeArray[i] as oppose to primeArray[k].