### Qualified's blog

By Qualified, history, 4 weeks ago,

Note: Factors and prime factorization are two different things. The factors of a number are the numbers that are divisible by it. Example: 12: {1, 2, 3, 4, 6, 12}.

• -20

 » 4 weeks ago, # |   -19 Yes
•  » » 4 weeks ago, # ^ |   0 Sir, thank you bro sir.
 » 4 weeks ago, # |   0 To do so, you need to first prime factorize the number. This can be done in $O(n)$ precomputation time and $O(\log n)$ per query. You can do so by keeping the smallest prime divisor of each number (for more details see here).Now that you have the number in its prime factorized form ${p_1}^{a_1}{p_2}^{a_2}{p_3}^{a_3}\ldots$, you can generate factors using a recursive approach. First note that all factors of this number are prime factorized to ${p_1}^{b_1}{p_2}^{b_2}{p_3}^{b_3}\ldots$ where $0 \leq b_i \leq a_i$. You can recursively generate all sequences of $b$ that satisfy this requirement and now you have all factors of the number.Note that this works in $O(\log n + k)$ time, where $k$ is the number of factors this number has. Check out highly composite numbers, which is an upper bound to $k$. I don't know of any ways to solve this problem without the $O(n)$ precomputation though.
 » 4 weeks ago, # | ← Rev. 2 →   +36 A number can have more than $O(\log{n})$ divisors ($O(\sqrt[3]{n})$ is a useful bound in practice, the actual bound is a little more involved, see https://math.stackexchange.com/questions/63687/bound-for-divisor-function ), and an algorithm that finds all divisors is bounded below by the number of divisors, so there is no algorithm for finding divisors in $O(\log{n})$ time.A number has $O(\log{n})$ prime factors, so you might be able to use that.
•  » » 4 weeks ago, # ^ |   0 Thanks for the informative explanation!