Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
It seems that perhaps this would require factoring numbers into prime factors first, which is notably slow. –  Vladhagen Jan 18 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 at 1:27

2 Answers 2

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

share|improve this answer

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.

share|improve this answer
    
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 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 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 at 1:36
    
@voldemort $5$ definitely divides $5!$. –  Patrick Da Silva Jan 18 at 1:36
    
@PatrickDaSilva: Sorry- stupid mistake. –  voldemort Jan 18 at 1:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.