Highest power of a prime $p$ dividing $N!$ How does one find the highest power of a prime $p$ that divides $N!$ and other related products?
Related question: How many zeros are there at the end of $N!$?

This is being done to reduce abstract duplicates. See 
Coping with *abstract* duplicate questions. and List of Generalizations of Common Questions for more details.
 A: de Polignac's formula named after Alphonse de Polignac, gives the prime decomposition of the factorial $n!$.
A: Largest power of a prime dividing $N!$
In general, the highest power of a prime $p$ dividing $N!$ is given by
$$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$
The first term appears since you want to count the number of terms less than $N$ and are multiples of $p$ and each of these contribute one $p$ to $N!$. But then when you have multiples of $p^2$ you are not multiplying just one $p$ but you are multiplying two of these primes $p$ to the product. So you now count the number of multiple of $p^2$ less than $N$ and add them. This is captured by the second term $\displaystyle \left \lfloor \frac{N}{p^2} \right \rfloor$. Repeat this to account for higher powers of $p$ less than $N$.
Number of zeros at the end of $N!$
The number of zeros at the end of $N!$ is given by $$\left \lfloor \frac{N}{5} \right \rfloor + \left \lfloor \frac{N}{5^2} \right \rfloor + \left \lfloor \frac{N}{5^3} \right \rfloor + \cdots$$ where $\left \lfloor \frac{x}{y} \right \rfloor$ is the greatest integer $\leq \frac{x}{y}$.
To make it clear, write $N!$ as a product of primes $N! = 2^{\alpha_2} 3^{\alpha_2} 5^{\alpha_5} 7^{\alpha_7} 11^{\alpha_{11}} \ldots$ where $\alpha_i \in \mathbb{N}$.
Note that $\alpha_5 < \alpha_2$ whenever $N \geq 2$. (Why?)
The number of zeros at the end of $N!$ is the highest power of $10$ dividing $N!$
If $10^{\alpha}$ divides $N!$ and since $10 = 2 \times 5$, $2^{\alpha} | N!$ and $5^{\alpha} | N!$. Further since $\alpha_5 < \alpha_2$, the highest power of $10$ dividing $N!$ is the highest power of $5$ dividing $N!$ which is $\alpha_5$.
Note that there will be 
 1. A jump of $1$ zero going from $(N-1)!$ to $N!$ if $5 \mathrel\| N$
 2. A jump of $2$ zeroes going from $(N-1)!$ to $N!$ if $5^2 \mathrel\| N$
 3. A jump of $3$ zeroes going from $(N-1)!$ to $N!$ if $5^3 \mathrel\| N$ and in general
 4. A jump of $k$ zeroes going from $(N-1)!$ to $N!$ if $5^k \mathrel\| N$
where $a \mathrel\| b$ means $a$ divides $b$ and $\gcd\left(a,\dfrac{b}{a} \right)$ = 1.
Largest power of a prime dividing other related products
In general, if we want to find the highest power of a prime $p$ dividing numbers like $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$, $\displaystyle P(N,r)$, $\displaystyle \binom{N}{r}$, the key is to write them in terms of factorials.
For instance, $$\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1) = \frac{(2N)!}{2^N N!}.$$ Hence, the largest power of a prime, $p>2$, dividing $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$ is given by $s_p((2N)!) - s_p(N!)$, where $s_p(N!)$ is defined above. If $p = 2$, then the answer is $s_p((2N)!) - s_p(N!) - N$.
Similarly, $$\displaystyle P(N,r) = \frac{N!}{(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle P(N,r)$ is given by $s_p(N!) - s_p((N-r)!)$, where $s_p(N!)$ is defined above.
Similarly, $$\displaystyle C(N,r) = \binom{N}{r} = \frac{N!}{r!(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle C(N,r)$ is given by $$s_p(N!) - s_p(r!) - s_p((N-r)!)$$ where $s_p(N!)$ is defined above.
A: For something completely different, see page 114 of Concrete Mathematics by Graham, Knuth, Patashnik. The highest power of a prime $p$ dividing $n!$ is $n$ minus the sum of the integer digits of $n$ in base $p$, all divided by $p-1$. In Mathematica you would write:
(n-Total[IntegerDigits[n,p]])/(p-1)

Hence, the number of trailing zeros of $n!$ is
(n-Total[IntegerDigits[n,5]])/4

I've found this method to be much faster than the sum of Floor functions...
A: Define $ e_p(n) = s_p(n!), $ as Marvis is using $s_p$ for the highest exponent function...
We get
$$ e_p(n) = s_p(n!) = \sum_{i \geq 1} \left\lfloor \frac{n}{p^i} \right\rfloor  $$
I thought I would prove this by mathematical induction. We need, for any positive integers $m,n,$
LEMMA: 
(A) If $n + 1 \equiv 0 \pmod m,$ then 
$$  \left\lfloor \frac{n + 1}{m} \right\rfloor = 1 +  \left\lfloor \frac{n}{m} \right\rfloor $$
(B) If $n + 1 \neq 0 \pmod m,$ then 
$$  \left\lfloor \frac{n + 1}{m} \right\rfloor =   \left\lfloor \frac{n}{m} \right\rfloor $$
For $n < p,$ we know that $p$ does not divide $n!$ so that $e_p(n) = s_p(n!)$ is $0.$ But all the $\left\lfloor \frac{n}{p^i} \right\rfloor$ are $0$ as well. So the base cases of the induction is true.
Now for induction, increasing $n$ by $1.$ 
If $n+1$ is not divisible by $p,$ then $e_p(n+1) = e_p(n),$ while part (A) of the Lemma says that the sum does not change. 
If $n+1$ is divisible by $p,$ let $s_p(n+1) = k.$ That is, there is some number $c \neq 0 \pmod p$ such that $n+1 = c p^k.$ From the Lemma, part (B), all the $\left\lfloor \frac{n}{p^i} \right\rfloor$ increase by $1$ for $i \leq k,$ but stay the same for $i > k.$ So the sum increases by exactly $k.$ But, of course, $e_p(n+1) = s_p((n+1)!) = s_p(n!) + s_p(n+1) = e_p(n) + k.$ So both sides of the middle equation increase by the same $s_p(n+1) = k,$ completing the proof by induction.
Note that it is not necessary to have $n$ divisible by $p$ to get nonzero $e_p(n).$ All that is necessary is that $n \geq p,$ because we are not factoring $n,$ we are factoring $n!$ 
A: Here's a different approach I found while thinking in terms of relating the sum of digits of consecutive numbers written in base $p$. Part of the appeal of this approach is you might have at one point learned that there is a connection but don't remember what, this gives a quick way to reconstruct it.
Let's consider $s_p(n)$, the sum of digits of $n$ in base $p$. How does the sum of digits change if we add $1$ to it? It usually just increments the last digit by 1, so most of the time,
$$s_p(n+1) = s_p(n)+1$$
But that's not always true. If the last digit was $p-1$ we'd end up carrying, so we'd lose $p-1$ in the sum of digits, but still gain $1$. So the formula in that case would be,
$$s_p(n+1) = s_p(n) + 1 - (p-1)$$
But what if after carrying, we end up carrying again? Then we'd keep losing another $p-1$ term. Every time we carry, we leave a $0$ behind as a digit in that place, so the total number of times we lose $p-1$ is exactly the number of $0$s that $n+1$ ends in, $v_p(n+1)$.
$$s_p(n+1) = s_p(n) + 1 - (p-1)v_p(n+1)$$
Now let's rearrange to make the telescoping series and sum over,
$$\sum_{n=0}^{k-1} s_p(n+1) - s_p(n) = \sum_{n=0}^{k-1}1 - (p-1)v_p(n+1)$$
$$s_p(k) = k - (p-1) \sum_{n=0}^{k-1}v_p(n+1)$$
Notice that since $v_p$ is completely additive so long as $p$ is a prime number,
$$s_p(k) = k - (p-1) v_p\left(\prod_{n=0}^{k-1}(n+1)\right)$$
$$s_p(k) = k - (p-1) v_p(k!)$$
This rearranges to the well-known Legendre's formula,
$$v_p(k!) = \frac{k-s_p(k)}{p-1}$$
A: Walking down the street I realized how to proof the formula in a very simple way. The key idea is to know how many numbers contain a given prime in the exact $q$-th power.
Let us denote the set of all numbers up to $n$ (inclusive) that are divisible by $q$-th power of prime $p$ but not divisible by the greater ($q+1, q+2, ...$) power of that prime:
$$
M^p_q(n) := \{ m : m \le n, p^q | m, p^{q+1} \nmid m\}
$$
How many numbers in that set? Well, obviously, the number of those that are divisible by $p^q$ minus the number of those which are divisible by $p^{q+1}$:
$$
|M^p_q(n)| = \bigg\lfloor \frac{n}{p^q}\bigg\rfloor - \bigg\lfloor \frac{n}{p^{q+1}}\bigg\rfloor
$$
OK. Each of the numbers in $M^p_q$ gives us the $q$-th power of $p$ in $n!$ so we need just add them all:
$$
s_p(n!)=\sum_{q=1}^{\infty}q|M^p_q(n)|
$$
Which is the desired result.
A: For a number $n$, define $\Lambda(n)=\log p$ if $n=p^k$ and zero elsewhen. 
Note that $\log n=\sum\limits_{d\mid n}\Lambda(d)$. If $N=n!$, then $$\log N=\sum_{k=1}^n\log k=\sum_{k=1}^n\sum_{d\mid k}\Lambda (d)=\sum_{d=1}^n \Lambda(d)\left\lfloor \frac nd\right\rfloor$$
Since $\Lambda(d)$ is nonzero precisely when $d$ is a power of a prime and in such case it equals $\log p$, the last sum equals $$\sum_{p}\sum_{k\geqslant 1}\log p \left\lfloor\frac n{p^k}\right\rfloor$$ and this gives $$\nu_p(n!)=\sum_{k\geqslant 1}\left\lfloor\frac n{p^k}\right\rfloor$$
If you write $n$ is base $p$, say $n=a_0+a_1p+\cdots+a_kp^k$, the above gives that $$\nu_p(n!)=\frac{s(n)-n}{1-p}$$ where $s(n)=a_0+\cdots+a_k$. 
A: $s_{p}(n!)=\sum_{i=1}^{\infty}[\frac{n}{p^i}]$
Since $n!$ is the product of the integers $1$ through $n$, we have at least one factor of $p$ in $n!$ for each multiple of $p$ in $\{1,2,\ldots ,n\}$, of which there are $[ \frac{n}{p}]$. Each multiple of $p^2$ contributes an additional factor of $p$, each multiple of $p^3$ contributes yet another factor of $p$, etc. Adding up the number of these factors gives the infinite sum for $s _{p}(n!)$.
A: This is essentially a variation on the answer by LRDPRDX.
For each $k\geq 1$ let $M_k$ denote the set of positive multiples of $p^k$, i.e, $M_k=\{a p^k: a\geq 1 \text{ and } ap^k\leq n\}.$ Observe that $M_{k+1}\subset M_k$, $M_k=\emptyset$ for $k>\lfloor n/(\log p)\rfloor$ and
$|M_k| = \lfloor p/n^k\rfloor$.
The $p$-adic valuation of $n!$ is clearly
$\begin{align}
&\sum_{k=1}^\infty k |M_k \setminus M_{k+1}| 
\\&= \sum_{k=1}^\infty k (|M_k| -  |M_{k+1}|) 
\\&= \sum_{k=1}^\infty k |M_k| - \sum_{k=2}^\infty (k-1)|M_{k}|
\\&= \sum_{k=1}^\infty k |M_k| - \sum_{k=1}^\infty (k-1)|M_{k}|
\\&= \sum_{k=1}^\infty  |M_k| = \sum_{k=1}^\infty \lfloor p/n^k\rfloor.
\end{align}$
