Is there any trick to find the number of divisors of any number? For e.g., a quick way to tell the number of divisors of 987655432 (chosen randomly)?

EDIT: And it has to be done without prime factorization.

  • 4
    $\begingroup$ Get the prime factorisation. If $n = \prod p_i^{k_i}$, then the number of divisors of $n$is $\prod (k_i+1)$. $\endgroup$ – Daniel Fischer Nov 2 '13 at 13:11
  • $\begingroup$ @DanielFischer I have edited the question now. $\endgroup$ – J.P. Nov 2 '13 at 13:13
  • 1
    $\begingroup$ Can you give more information about the motivation for this question? Why is it that you need a way to do this without prime factorization? What leads you to believe/hope that there is such a way? $\endgroup$ – Cameron Buie Nov 2 '13 at 13:20
  • 1
    $\begingroup$ There is at least a name for this divisor function, $d(n) = \sigma_0(n)$, the number of (positive) divisors of $n \ge 1$. It corresponds to one of the early OEIS sequences. $\endgroup$ – hardmath Nov 2 '13 at 13:20

Consider the natural number $987655432$. Using prime factorization (and hating our lives while using it, lol) we see that $987655432=2^3\cdot 1033\cdot 119513$. By the Fundamental Theorem of Arithmetic, each factor is of the form $2^a\cdot 1033^b\cdot 119513^c$ where $0\leq a \leq 3$, $0\leq b\leq 1$, and $0\leq c \leq 1$. We see that there are $4$ choices for $a$, $2$ choices for $b$, and $2$ choices for $c$. By the Multiplication principle, the number of factors is $4\cdot 2 \cdot 2=16$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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