×

# Number theory

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

Note by Goutam Narayan
3 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$$

- 3 years, 9 months ago

I think it should be $$p^j \leq n$$

- 3 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$.

- 3 years, 8 months ago

He asked for an algorithm. A code with your algo would run for an infinite time.

- 3 years, 8 months ago

Oh! I think I missed the word 'algorithm'. But I don't think the OP meant algorithm literally [It's tagged with number theory]. Despite that, you're right. That algorithm will go on forever in the natural sense. I just posted that because I think that looks cool :)

- 3 years, 8 months ago

×