Qualified's blog

By Qualified, history, 4 weeks ago, In English

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}.

  • Vote: I like it
  • -20
  • Vote: I do not like it

4 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it


4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +36 Vote: I do not like it

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.