# Number of factors in $972$

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.

• Why the downvote? Nov 6, 2016 at 23:44

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

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

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.

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

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

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

• 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. Dec 6, 2016 at 16:17