Prime with highest power that divides $N$

Question

Given a natural number $n$, how can I find the prime $p$ with highest power $e$ in the prime factorization of $n$.
E.g: $n=12=2^2.3$
$\therefore p=2 \ \ and\ \ e=2. $
E.g 2: $n=450=5^2 * 3^2 * 2^1$ So the prime with highest power is 3 or 5. We can print any of them as a valid answer.
I can prime factorize a number in $O(logn)$ for $n<10^6$. How shall I solve this problem for $n$ upto $10^{12}$.

Answer 1

Since $n$ is bounded, this is a great way to use a look up table.

As there are approximately

$$\pi(n) \approx \frac{n}{\ln(n)}$$

which is your case equals only $\frac{10^6}{\ln(10^6)}\approx78498$ possible prime factors. This should be the fastest approach.