Prime factorization of n!

Rather than the conventional ways of prime factorization, there is an easy way to do the prime factorization of n!. First of all you have to list out all the prime numbers less than or equal to n. It is because 

n! = 1 x 2 x 3 x 4 x 5 x .... x n 

So prime factors of n! are all the prime numbers less than n. Next we have to find out the multiplicity of each of these prime factors. 

In the prime factorization, for example, 

60 = 2 x 2 x 3 x 5 

the multiplicity of the prime factor 2 is 2, while the multiplicity of each of the prime factors 3 and 5 is 1. Thus, 60 has 4 prime factors, but only 3 distinct prime factors. 

Now, if m is the largest prime number less than or equal to n, 

n! = 2^m1 x 3^m2 x ... x m^p 

Now we have to find out these multiplicities m1, m2, ..... ,p of prime factors. 

Let’s take an example of 10! 

Prime numbers less than 10 are 2,3,5,7 

10! = 2^m1 x 3^m2 x 5^m3 x 7 

We already know there will one prime factor of 7 in 10! (1 x 2 x ... x 7 x... x 10). 

We have to find m1, m2 and m3 corresponding to 2, 3 and 5. 

There are five multiples of 2 between 1 and 10. 

2 x 1 , 2 x 2 , 2 x 3 , 2 x 4 , 2 x 5 

There are two multiples of 2 between 1 and 5. 

2 x 1, 2 x 2 

There is only one multiple of 2 between 1 and 2. 

2 x 1 

Thus multiplicity of the prime factor 2 is m1 = 5 + 2 + 1 = 8. 

Similarly, 

There are three multiples of 3 between 1 and 10. 

3  x 1 , 3 x 2 , 3 x 3 

There is only one multiple of 3 between 1 and 3. 

3 x 1 

Thus multiplicity of the prime factor 3 is m2 = 3 + 1 = 4. 

Similarly, 

There are two multiples of 5 between 1 and 10. 

5 x 1 , 5 x 2 

Thus multiplicity of the prime factor 5 is m3 = 2. 

So the prime factorization of 10! is as follows 

10! = 2⁸ x 3⁴ x 5² x 7 

Once you get the idea, its easier to do the prime factorization of factorials.