Prime with highest power that divides $N$ 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&lt;10^6$. How shall I solve this problem for $n$ upto $10^{12}$.
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.
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.