# Factorials and Prime Factors

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.

-
It seems that perhaps this would require factoring numbers into prime factors first, which is notably slow. – Vladhagen Jan 18 '14 at 1:25
I'm writing a program to do this so the slow part shouldn't be a problem. How would I go about doing that? – Bradg89 Jan 18 '14 at 1:27

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

-

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.

-
I'm lost. Could you explain how I could get 5!=(2^3)(3^1)(5^1) without actually calculating 5!=120 using 5 for the example. – Bradg89 Jan 18 '14 at 1:33
@Bradg89 : The argument is that to calculate the prime powers dividing $5!$, you just have to find the prime powers of $p \le 5$ a prime that divide $1,2,3,4,5$ for each $p$, and then multiply them together. For the prime $2$, $2$ divides $2$ once and $4$ twice ; $3$ divides only $3$ once, and $5$ divides only $5$ once. Thus this gives $5! = (2^1 \cdot 2^2) \cdot (3^1) \cdot (5^1)$. Running the algorithm is essentially factoring the integers from $1$ to $n$. This is the same argument as in André's answer, except that André has smartly made the count for you in advance. – Patrick Da Silva Jan 18 '14 at 1:35
The only primes that can divide $5!$ are $2$ , $3$ and $5$. Now $\floor{5/2}=2. \floor{5/2^2}=1$. So the power of 2 in your decomposition is $2+1=3$. Similarly $\floor{5/3}=1$, and the power of $3$ in your decomposition is $1$. Same for $5$. – voldemort Jan 18 '14 at 1:36
@voldemort $5$ definitely divides $5!$. – Patrick Da Silva Jan 18 '14 at 1:36
@PatrickDaSilva: Sorry- stupid mistake. – voldemort Jan 18 '14 at 1:37