Waste less time on Facebook — follow Brilliant.
×

Number theory

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

Note by Goutam Narayan
3 years, 9 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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\)

Bogdan Simeonov - 3 years, 9 months ago

Log in to reply

I think it should be \(p^j \leq n\)

Labib Rashid - 3 years, 9 months ago

Log in to reply

True. But you could save yourself from the trouble by just putting \[\displaystyle \sum_{i=1}^\infty \lfloor\frac{n}{p^i}\rfloor\].

Mursalin Habib - 3 years, 8 months ago

Log in to reply

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

Labib Rashid - 3 years, 8 months ago

Log in to reply

@Labib Rashid 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 :)

Mursalin Habib - 3 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...