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

Solution 1:

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!

Solution 2:

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].

Solution 3:

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)

Solution 4:

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)
    }
  }
}