Prime Power in a Factorial — Solution & Editorial

Back to the Problem

Legendre's formula: ∑_k≥1 ⌊N / P^k⌋, summed until P^k exceeds N.

Complexity: O(log_P N)