Prime Factoring Factorials

A lot of number theory problems depend on prime factoring. To solve these problems for factorial numbers requires an easy way to prime factor factorials.

The standard way of prime factoring is to take the number to factor and start dividing it by 2 to see how many times 2 goes into the number. Then move on to 3, 5, and the remaining primes. For example:

 2|1500 2|750 3|375 5|125 5|25 5 1500 = 22·3·53

To prime factor 41! determine how many times 2 go into 33,452,526,613,163,807,108,170,062,053,440,751,665,152,000,000,000.

Dividing a 50 digit number by 2 is more than I want to do; especially the number of times we'll need to do it to determine the exponent for 2. We need to think of a better way to do this.

Where does the exponent for 2 come from? To get 41! we multiply all the numbers from 2 to 41. Every multiple of 2 contributes 1 to the exponent; every multiple of 4 contributes an additional 1 to the exponent; etc.:

 Multiples of 2: 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 (20) Multiples of 4: 4 8 12 16 20 24 28 32 36 40 (10) Multiples of 8: 8 16 24 32 40 (5) Multiples of 16: 16 32 (2) Multiples of 32: 32 (1)

The exponent for 2 is the sum of all of these ones: 20 + 10 + 5 + 2 + 1 = 38.

The counts for the various multiples can be determined by repeated division by 2, discarding any remainder:

 2|41 2|20 2|10 2|5 2|2 1

We need to do this for the remaining primes through 19. (The primes 23 and larger cannot have exponents greater than 1 since 23 · 2 > 41.)

 3|41 5|41 7|41 11|41 13|41 17|41 19|41 3|13 5|8 5 3 3 2 2 3|4 1 1

Adding the quotients for each set of divisions gives us the exponents for each prime.

 41! = 238 · 318 · 59 · 75 · 113 · 133 · 172 · 192 · 23 · 29 · 31 · 37 · 41

[Back]