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

enter image description here

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?

• miracle173: I don't know JavaScript. But how does it handle division /. Is this an integer division or is this a floating point division? If it is floating point, can there occur rounding errors if you have a large n and do a lot of divisions? Usually one uses integer arithmetic for such calculations

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.

• Teepeemm: Or use i*i<=n.
• miracle173: @Teepeemm But you have still a lot of integer multiplications that are not needed if you calculate the root before the loop.