Quick way to find the highest multiplicity of a divisor of a number? Not sure if worded properly.
For instance, the highest multiplicity of 2 in 60 is 2 because the prime factorization of 60 is 2^2*3*5.
For 16, the highest multiplicity of 2 would be 4, etc. Is there a good way to find this without constantly dividing 60 by 2 and counting how many times you end up with a whole number?
 A: Problem: Given $x,$ find whether 2^d is a factor of $x.$
Using the Euclidean algorithm, which is fast (see: 1, 2, 3), we have
$$\gcd(x, 2^{\lceil{\log_2{x}}\rceil}) =
\begin{cases}
2^d & \text{if } 2^d \mid x \\
1 & \text{if } 2^d \not\mid x
\end{cases}$$
Edit for clarification:
If $2^d$ is a factor $x$, then $x = y 2^d$, where $y$ is the rest of factors. Then we can clearly see that $\gcd(y2^d, 2^d) = 2^d).$ If $2^d$ is not a factor of $x,$ then $\gcd = 1.$
The ceiling business makes sure that we cover the largest possible $d.$ I.e., find a bound $b$ such that $x \le 2^b.$ Take $\log$ both sides.. rest is exercise.
A: Here's a relatively simple approach with fewer division operations.
Start with number $n$ and possible divisor $d$.
Divide $n$ by $d$ to get $n_1$; divide $n_1$ by $d^2$ to get $n_2$;
divide $n_2$ by $d^4$ to get $n_3$; and so forth, each time squaring the power of $d,$
until you find a number $n_k$ that is not divisible by $d^{2^k}.$
At this point you know that $n = d^{2^k - 1} n_k$
and that the multiplicity of the divisor $d$ in $n_k$ is at most $2^k - 1.$
Let $p_k = 0.$
Let $m_k = n_k.$
For $i = k, k-1, k-2, \ldots, 1$ in turn,
let $m_{i - 1} = m_i/d^{2^{i - 1}}$ and let $p_{i - 1} = p_i + 2^{i - 1}$
if $m_i$ is divisible by $d^{2^{i - 1}}$;
otherwise let $m_{i - 1} = m_i$ and let $p_{i - 1} = p_i.$
When you have computed $m_0,$ then $p_0$ will be the multiplicity of $d$ as a divisor of $n_k.$
Then the multiplicity of $d$ as a divisor of $n$ is $2^k - 1 + p_0.$
The number of divisions that must be performed is $O(\log(p))$ where $p$ is the multiplicity of $d$ as a divisor of $n,$
so the number of divisions is $O(\log\log(n)).$
I think you may be able to get similar big-O performance from the Euclidean algorithm mentioned in another answer if you use that technique to perform a binary search for the largest power of $d$ that divides $n.$ I just think this method is a bit simpler and may have a lower constant factor.
