2
$\begingroup$

Question: How many factors does $972$ have?

I listen them all out and got $18$. Which is a notourisly inefficient method.

So I'm wondering, if there is an algorithm for finding all the factors of a number, and what is the proof.

$\endgroup$
1
  • 1
    $\begingroup$ Why the downvote? $\endgroup$
    – Frank
    Nov 6, 2016 at 23:44

3 Answers 3

6
$\begingroup$

.Prime factorize $972$ first. This has to be done, otherwise there are extremely complicated algorithms, such as the elliptic curve factorization algorithm that do the job for ordinary numbers. Since $972$ is small, we can do our work by hand.

$$972 = 2\cdot 486 = 2\cdot 2\cdot 243 = 2\cdot 2\cdot 3\cdot 81 = 2\cdot 2\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3 = 2^23^5$$.

Now, any factor of $972$ comes from choosing numbers $0 \leq i \leq 2$, $0 \leq j \leq 5$, because then $2^i3^j$ is a factor of $972$.

Now, there are $3$ choices of $i$ and $6$ choices of $j$, hence the number of factors is $3\cdot 6=18$. This way, we do not need to write down the factors as well.

$\endgroup$
4
  • $\begingroup$ Better method than mine! Nice! :) $\endgroup$
    – Frank
    Nov 5, 2016 at 15:46
  • $\begingroup$ @Frank Have I answered your question? Or is there something else you want answered? $\endgroup$ Nov 5, 2016 at 15:48
  • $\begingroup$ Nah, I'm fine. The second half is answered in another answer. $\endgroup$
    – Frank
    Nov 5, 2016 at 15:49
  • $\begingroup$ Great. That's very good. $\endgroup$ Nov 5, 2016 at 15:50
1
$\begingroup$

If there were an (efficient enough) algorithm for that, then the RSA cryptosystem, which depends on factoring being hard, would be broken. So no, there's no easy algorithm yet known.

But for small numbers like yours, the Sieve of Eratosthenes is a not-bad place to start, and you only need to work up to about 35 or so, since if you find a factor $f$ bigger than $\sqrt{N}$, then $N/f$, which is less than $\sqrt{N}$, is also a factor, so you would have found it already.

$\endgroup$
2
  • $\begingroup$ What's an RSA cryptosystem? I'm not too familiar with math programs such as Mathematica, Pari, PLSQ etc. Could you please explain? $\endgroup$
    – Frank
    Nov 5, 2016 at 15:46
  • $\begingroup$ See google.com/…. $\endgroup$ Nov 5, 2016 at 15:46
0
$\begingroup$

$$972=2^2\times3^5$$ Therefore, total number of factors must be

$$(2+1)\times(5+1)=18$$

$\endgroup$
1
  • 3
    $\begingroup$ Please don't answer old questions which have already been answered if you have nothing new to add - even more so in the case of really trivial questions like this. $\endgroup$
    – Alex M.
    Dec 6, 2016 at 16:17

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.