Number of factors in $972$

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

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