3
\$\begingroup\$

This is my code:

export function all_divisors(num: number): number[] {
    return range(1, num+1).filter(i => num % i === 0).toArray();
}

the range function(docs) is part of the IterPlus library and is a pretty self-explanatory inclusive-exclusive range function, again, what I'm doing using the filter function is pretty self-explanatory, .toArray() converts IterPlus<number> to an array number[].

Anyway, I'd like some help optimizing this, as it is pretty slow when working with larger numbers(it took ~190ms for 3,000,000 and ~3ms for 30,000).

I don't care about code-golfing, or meant to code-golf in the first place, it was just convienient at the time.

\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Welcome to Code Review!

When factorising a number, you have the property that; if a number \$ a \$ is factor of \$ n \$, then \$ \frac{n}{a} \$ is also a factor of \$ n \$.

This immediately reduces your loop from \$ 1..n \$ by half to \$ 1..\frac{n}{2} \$.

Now, another optimisation to be done could be memoisation taking into account the property above. If the number \$ \frac{n}{a} \$ is a factor, then all factors of this number would also be factors for your original number \$ n \$.

Next step you can think about is checking only for prime factors, and then using the memoisation of factors from above.

There are several other factorisation algorithms to efficiently calculate. Take a look at some of such algorithms discussed in this article. (https://cp-algorithms.com/algebra/factorization.html)

\$\endgroup\$
2
  • 2
    \$\begingroup\$ You did not mention it, but with the "another optimisation" you would just have to loop from 1 to sqrt(n). So it would be O(sqrt(n)) instead of O(n) \$\endgroup\$
    – jjj
    Commented Dec 17, 2020 at 17:04
  • \$\begingroup\$ @jjj i was more guiding the op about how thought process for optimisations go. you don't hit the perfect solution in first attempt. also, the link i shared covers the prime factorisation in it \$\endgroup\$
    – hjpotter92
    Commented Dec 17, 2020 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.