# Primes help

Printable View

• May 12th 2009, 05:32 PM
amma0913
Primes help
I need help with this question please!

Create a formula (using sigma, logs, floor function) that computes the exponent of any particular prime in the prime factorization of a given factorial.

we use the notation
exp(p, n!) = the exponent of prime p in the prime factorization of n!

Example: exp(5, 25!) = 6

help please!
• May 12th 2009, 09:01 PM
Media_Man
A Simple Formula
$exp(p, n!) = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^i}\rfloor$

For example, 625! contains 125 multiples of 5, 25 multiples of 25, 5 multiples of 125, and 1 multiple of 625, thus $exp(5, 625!) = 125+25+5+1 = 156$ .

If you're actually going to use this in practice, the $\infty$ is not necessary. Since $\lfloor \frac{n}{p^i}\rfloor = 0$ for $n , you only have to sum up to $i=\lfloor \frac{ln(n)}{ln(p)} \rfloor$ , but that doesn't make for as pretty of a formula.