Блог пользователя Qualified

Автор Qualified, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

Yes

»
3 года назад, # |
  Проголосовать: нравится 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.

»
3 года назад, # |
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.