Prime Factorization of Factorials

In a previous post I wrote how the sum of the integers from one to n could be calculate with the formula 0.5*n*(n+1).  Then I started to wonder if there was something similar for the product of the integers from one to n, or n!, other than just brute force?

By the fundamental theorem of arithmetic n! can be written as it’s prime factorization, which will be the product of all the primes between 1 and n, inclusively, to some power.  The trick is to calculate the powers for each prime number.  Consider the prime factorization of all the numbers from one to n.  It’s obvious than any prime greater than n/2, denote this number k, has a power of one since there will exist no other number between one and n that k will divide.  To write this in a more formal way, let S={2,3,5,7,11,13,…p} be the ordered set of primes which divide n.  S has finite order, m, and p is the largest prime dividing n.  Let R={r1,r2,r3,…,rm} be the set of powers for each prime number.  Then n! factorial can be written as

$n!=\prod\limits_{i} s_i^{r_i}=2^{r_1}*3^{r_2}*5^{r_3}*...*p$

Here’s an example of how to find 10!.  The prime factors between one and ten are 2, 3, 5, and 7 so S={2,3,5,7}.  Then 10! can be written in the form:

$10!=(2^a)*(3^b)*(5^c)*7$

First compute two’s power.  There are five numbers between one and ten that two divides into.  These numbers are given 2*1, 2*2, …, 2*5.  Further, two also divides two numbers in the set {1,2,3,4,5}.  These numbers are 2*1 and 2*2.  Continuing in this pattern, there is one number between one and two that two divides into.  Then a=5+2+1=8.

Now look at finding three’s power.  There are three numbers from one to ten that three divides into, and then one number between one and three that three divides into.  Thus b=3+1=4.  In a similar fashion c=2.  Then the set R={8,4,2,1}.  The final answer is:

$10!=2^8*3^4*5^2*7$

1 Response to “Prime Factorization of Factorials”

1. 1 Interview Street – Equations(Math) « About Algorithms And CSE puzzles Trackback on June 21, 2012 at 11:24 AM