Algorithm to find the maximum power of N that divides M factorial (M!)

Reading time: 40 minutes | Coding time: 10 minutes

We are given two numbers M and N. Our aim is to find the highest power of N that divides Factorial of M (M!). We often come across such problems in competitive programming where we require an optimal solution.

First we will discuss about the Brute Force approach and then we will be discussing this problem using Legendre’s formula.

Underlying are some examples which would help in better understanding of the problem.

EXAMPLES

Input : M = 5, N = ...