I am looking for an efficient algorithm to compute what I'd call the "partial square root" of an integer. In more formal terms:
Given a positive integer $k$, find the pair of positive integers $(r,n)$ with the smallest $n$ such that $k=r^2n$.
Naively, one could start with $(r,n)=(1,k)$, iterate over all $p \in \{2,3,5,7,...,2i+1\}$ (as a stand-in for all the primes), and while $n/p^2$ is integer, compute $(r',n')=(rp,n/p^2)$, but something tells me that there should be a more more efficient way to accomplish this.
One way to accomplish the task is to factor $k=\prod p_i^{a_i}$ where $p_i$ are primes that divide $k$.
Then, for each instance in which an exponent $a_i$ is odd, call them $a_j$, use the corresponding prime base to form the product $n=\prod p_j$.
The quotient $\frac{k}{n}$ will then have only prime factors with even exponents, and hence will be a square, $r^2$.
You cannot make $n$ smaller by removing one or more of the $p_j$ from its definition, as that will leave one or more of the remaining $p_i$ in $\frac{k}{n}$ with an odd exponent, and that cannot be a square.