# This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.To simplify a fraction you find the greatest common denominator (GCD) and divide both the numerator and the denominator by it.

Iterating through the smaller number is sufficient for the problem for \mathcal{O}(\sqrt{min(N, D)})

However a faster algorithm is using Euclidâ€™s algorithm for GCD.

## Time complexity

\mathcal{O}(\log min(N, D))