Trailing zeroes

A week or so ago someone mentioned the following problem:

How many trailing zeroes does 1000! have [when written out in base ten, of course]?

Easy enough to find...

Prelude> length $ takeWhile (== '0') $ reverse (show (product [1..1000])) 
249
Prelude>

But is there a better way? Yes, there is. After reading that someone said he did it in his head, the way to do it in your head occurred to me. *slaps forehead*

1000!, like any positive integer, has a unique prime factorization. In particular, we're interested in the primes 5 and 2, because 10 is 5 * 2. They certainly both appear in the prime factorization of 1000!, and they thus have positive exponents in said factorization. Let m be the exponent for 5, and let n be the exponent for 2. How to calculate them? Let's start with five.

• There are 200 multiples of 5 between 1 and 1000.
• There are 40 multiples of 25 between 1 and 1000.
• There are 8 multiples of 125 between 1 and 1000.
• There's 1 multiple of 625 between 1 and 1000.

You recognize, of course, that 5, 25, 125, and 625 are positive powers of 5. The multiples of 625 contribute four to m. The multiples of 125 contribute 3... but one of them is 625, so we don't want to count things more than once. Ditto for multiples of 25 and multiples of 5... but there's an easy way to make sure you get the right count: just add 200, 40, 8, and 1. That counts multiples of 25 twice, as they should be, multiples of 125 three times, and multiples of 625 four times. The sum: 249. Looks familiar.

So, how about 2?

• There are 500 multiples of 2 between 1 and 1000...

Hey, wait a minute. That's already way bigger than 249, so the minimum of m and n is exactly 249, and that's our answer, because it takes a five and a two to have a ten in the product, and there are exactly as many trailing zeroes as there are powers of 10 in 1000!