A simple JavaScript function that does prime factorization

Question

This is a simple JavaScript function that does prime factorization.

I wrote it on an Android phone with online editor (I don't have access to computers in night time):

Code:

function factorize(n) { if (!(Number.isInteger(n) && n >= 2)) { throw 'Input is invalid' } const factors = [] while (n % 2 == 0) { factors.push(2) n /= 2 } for (let i=3; i<=Math.round(Math.sqrt(n)+1); i+=2) { while (n % i == 0) { factors.push(i) n /= i } } if (n > 1) { factors.push(n) } return factors } console.log(factorize(31556952)) 

Output

> Array [2, 2, 2, 3, 3, 3, 3, 3, 3, 7, 773] 

The test number is the number of seconds in a Gregorian year.

How can it be improved?

Answer 1

Taking a square root is a very slow operation, so it's a bad idea to do it for every iteration of the loop. Rather, you should only update the limit whenever n changes.