# How to efficiently find the largest perfect square dividing a given large integer?

Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite.

At present I am factorizing the number $n$ to find the highest number $q$. I need a better approach which does not involve to factorize the number $n$ completely or by some other approach which is less than $O(\sqrt n)$. Constraint: $n\leq 10^{18}$

some test cases:

• if $n=180$ then $q=6$
• if $n=17$ then $q=1$
• if $n=10000$ then $q=100$
• Is there a reason you think there is such an algorithm? – Thomas Andrews Jul 19 '14 at 14:27
• I think you still need to break down that number by the multipliers. And then to make up the number. Using multipliers. Which Degree a multiple of 2. – individ Jul 19 '14 at 15:09
• @individ I already did this but this approach times out i.e why I asked for the better approach – user157920 Jul 19 '14 at 15:56
• @ThomasAndrews those who did this question didn't factorize n completely so that is why i thought if there is a such an algorithm. – user157920 Jul 19 '14 at 15:57
• @barto when you edit a post, consider giving it a title better than "need help in number theory problem" – user147263 Jan 24 '15 at 20:38