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