Groups
Category
Legendre's formula gives the exponent of a prime p in n! by summing how many multiples of p, p^2, p^3, ... are ≤ n.
The Harmonic Lemma says that the values of \lfloor n/i \rfloor only change about 2\sqrt{n} times, so you can iterate those value blocks in O(\sqrt{n}) instead of O(n).