I need to write a program to input a number and output it's factorial in the form:
$4!=(2^3)(3^1)$
$5!=(2^3)(3^1)(5^1)$
I'm now having trouble trying to figure out how could I take a number and get the factorial in this format without actually calculating the factorial.
Say given 5 need to get result of $(2^3)(3^1)(5^1)$ without actually calculating 5!=120.
On
Note that $n!=1.2....n$. You are looking for all the primes dividing $n!$. Notice that the only primes that can divide $n!$ are $\leq n$. Now you have to calculate their powers.
For example the "power" of $2$ in $n!$ is $n!/2+n!/4+...$. (Here $n!/2$ means the integer closest to $n!/2$)
Similar formula holds for all other primes as well.
If $p$ is a prime, then the highest power $p^k$ of $p$ that divides $n!$ is given by $$k=\left\lfloor\frac{n}{p}\right\rfloor+ \left\lfloor\frac{n}{p^2}\right\rfloor+ \left\lfloor\frac{n}{p^3}\right\rfloor+ \cdots.\tag{1}$$
Here $\lfloor x\rfloor$ is the floor function, defined by $\lfloor x\rfloor$ is the greatest integer $\le x$.
Note that the sum in (1) is a effectively a finite (and usually short) sum: If $p^a\gt n$ then $\lfloor n/p^a\rfloor=0$.