# Tag Info

One common way to work with binomial coefficients without overflow is to use prime factorisation. Legendre discovered the formula for this, and it is worth proving it for yourself. The factorial of a number can be factorised as powers of primes: $$n! = p_1^{q_1} p_2^{q_2} \cdots$$ where: q_i = \sum_{k=1}^{\left\lfloor \log_{p_i} n \right\rfloor} \left\...