×

# Number theory

What is the algorithm to find exponent of a prime p in n! ?

Note by Goutam Narayan
2 years, 9 months ago

Sort by:

The highest power of p that divides n! is

$$\displaystyle\sum_{i=1}^{j}\left \lfloor \frac{n}{p^i} \right \rfloor$$

,where j is the biggest integer, for which $$p^j<n$$ · 2 years, 9 months ago

I think it should be $$p^j \leq n$$ · 2 years, 9 months ago

True. But you could save yourself from the trouble by just putting $\displaystyle \sum_{i=1}^\infty \lfloor\frac{n}{p^i}\rfloor$. · 2 years, 9 months ago

He asked for an algorithm. A code with your algo would run for an infinite time. · 2 years, 9 months ago