3
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ 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 \$\endgroup\$ Commented May 27, 2022 at 9:06

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Or use i*i<=n. \$\endgroup\$ Commented Apr 26, 2022 at 1:40
  • \$\begingroup\$ @Teepeemm But you have still a lot of integer multiplications that are not needed if you calculate the root before the loop. \$\endgroup\$ Commented May 27, 2022 at 8:30

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.