Running time complexity of finding maximal power of divisor that divides natural number
Here is one more approach you could consider, depending on whether you care more about theoretical running time or pragmatic solutions:


Use binary search to find the smallest $k$ such that $p^{2^k}|n$ but $p^{2^{k+1}}\not|n$.
Compute $m = (n/p^{2^k}) \bmod p^{2^k}$.
Recursively find the smallest $i$ such that $p^i|m$ but $p^{i+1}\not|m$.


(In the third step, you know $0 \le i &lt; 2^k$, so you have a narrower range for your search, and $m$ is smaller than $n$, so you are working with smaller numbers.)

Then it follows that the solution to your problem is $e=2^k + i$.

Note that $k \le \lg {\log n \over \log p}$, so you can find $k$ with binary search in $O(\log \log {\log n \over \log p})$ steps, where each step does a single trial division.  In the worst case, $m$ might not be much smaller than $n$, so this might not save you much.  But in many cases, $m$ will be vastly smaller than $n$, so step 3 is a lot easier than the original problem.  In particular, on average $m$ will be on the order of magnitude of $\sqrt{n}$ or less, so heuristically we might expect that after $\lg \lg n$ recursions we're dealing with constant-sized numbers, and heuristically we might expect the total running time to be dominated by step 1.  This won't always be true in the sense of worst-case complexity, though.