On this page
To find the highest power of 2 that divides 100!, you don't multiply anything out. You count the factors of 2 hidden inside 1 × 2 × 3 × … × 100. Legendre's formula does that count in about six lines of arithmetic, and the answer is 97.
What is Legendre's formula?
For a prime p and a positive integer n, the exponent of p in n! is ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …, and the terms become zero once the power of p is larger than n (Legendre's formula, Wikipedia). The formula is named after Adrien-Marie Legendre, and the same page cites his *Théorie des Nombres* (Paris, 1830).
The ⌊x⌋ sign is the greatest integer function. If it still feels shaky, read our guide to greatest integer and fractional part functions first.
Here is why the formula works. ⌊n/p⌋ counts the multiples of p up to n, and each one gives one factor of p. Multiples of p² carry a second factor, which ⌊n/p²⌋ picks up. Multiples of p³ carry a third factor, and so on. Every factor of p gets counted exactly once.
What is the highest power of 2 that divides 100!?
Divide by 2, 4, 8 and so on, and round each result down:
⌊100/2⌋ = 50 (every even number)
⌊100/4⌋ = 25
⌊100/8⌋ = 12
⌊100/16⌋ = 6
⌊100/32⌋ = 3
⌊100/64⌋ = 1
128 is bigger than 100, so you can stop. The total is 50 + 25 + 12 + 6 + 3 + 1 = 97.
So 2⁹⁷ divides 100!, but 2⁹⁸ does not. The OEIS entry A011371 describes its sequence as the "highest power of 2 dividing n!" and gives the same floor sum. It also gives the recursion a(n) = ⌊n/2⌋ + a(⌊n/2⌋).
That recursion gives you a quicker method. Halve 100 and round down, then halve the result, and keep going: 50, 25, 12, 6, 3, 1. You never have to work out 64 or 128.
You can check the answer a second way. Wikipedia gives the formula as (n − sₚ(n))/(p − 1), where sₚ(n) is the sum of the digits of n written in base p (Legendre's formula). In binary, 100 is 1100100, which has three 1s, so the exponent is (100 − 3)/1 = 97.
How many zeros are at the end of 100!?
Each zero at the end of a number comes from a factor of 10 = 2 × 5. 100! has 97 factors of 2 and far fewer factors of 5, so the 5s decide the count. ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24. The OEIS entry A027868 lists the "number of trailing zeros in n!" and gives a(100) = 24.
The usual mistake is to stop at ⌊100/5⌋ = 20. But 25, 50, 75 and 100 each contain two factors of 5, and the ⌊100/25⌋ term picks up the second one. The same OEIS page gives 249 zeros for 1000!, and you can check it: 200 + 40 + 8 + 1 = 249.
How do you find the power of 12 (or any composite) in n!?
Legendre's formula only works for primes. For a composite base, first split it into primes, just as you would when counting the divisors of a number.
12 = 2² × 3, so each 12 needs two 2s and one 3. For 100!:
Exponent of 2: 97, from the working above.
Exponent of 3: ⌊100/3⌋ + ⌊100/9⌋ + ⌊100/27⌋ + ⌊100/81⌋ = 33 + 11 + 3 + 1 = 48.
Pairs of 2s available: ⌊97/2⌋ = 48. 3s available: 48.
The power of 12 is the smaller of these two: min(48, 48) = 48.
So the highest power of 12 that divides 100! is 12⁴⁸. Here the two counts tie. Now try 50!. The 2s give 25 + 12 + 6 + 3 + 1 = 47, which makes ⌊47/2⌋ = 23 pairs. The 3s give 16 + 5 + 1 = 22. So the answer is 12²², and this time the 3s run out first.
A checklist for factorial-power questions
Split the base into primes (10 = 2 × 5, 12 = 2² × 3, 18 = 2 × 3²).
Work out Legendre's sum for each prime, using repeated division.
Divide each count by that prime's power in the base, and round down.
The smallest result is your answer.
Check every prime. The largest one does not always run out first.
Check one count with the base-p digit-sum formula.
For more divisibility practice, see our roundup of IOQM number theory questions. If your answer doesn't match the book's, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning, so you can find the line where your count went wrong. If floor functions or prime factorisation are the real gap, the Fermi Concept Library covers every concept in mathematics, each with its own lesson.
