Suppose you have a number
$$
N = p\_1^{e\_1}p\_2^{e\_2}\cdots p\_k^{e\_k}
$$
and are looking for the largest divisor $d|N$ such that $d^2<N$ (that is, [A060775](https://oeis.org/A060775)$(N)$.) How can I efficiently find this $d$?


If $N$ has a small number of divisors, you can just iterate through them all (keeping the best at each step). If $e\_i$ is large for some $i$, then you can search the divisors $d$ of $N/p\_i^{e\_i}$ less than $\sqrt{N}$ and find
$$
e=\min\left(\left\lfloor\frac{\log(\lfloor\sqrt{N-1}\rfloor/d)}{\log p\_i}\right\rfloor, e\_i\right)
$$


(this would be



```
s=sqrtint(N-1);
f=factor(N);
e=min(logint(s\d, f[i,1]), f[i,2])

```

in [PARI/GP](https://pari.math.u-bordeaux.fr/); presumably lots of languages have efficient implementations)


giving $p\_i^ed$ as the number to test. But for the general case where $k$ is large neither is practical. Is there some method which takes significantly fewer than $\tau(N)$ steps? You can assume that the factorization is given.



Efficiently finding the largest divisor of N less than sqrt(N)
I believe the Schroeppel & Shamir algorithm [1] can be adapted for use here, with time something like $O\left(\sqrt{\tau(n)}\omega(n)\right)$ and space something like $O\left(\sqrt[4]{\tau(n)}\right)$. The basic idea is splitting the prime powers into four sets with roughly the same number of divisors each, listing the divisors, and generating divisors from two pairs of two sets dynamically using min-heaps, and combining as expected.


[1] Richard Schroeppel and Adi Shamir, [A $T = O(2^{n/2})$, $S = O(2^{n/4})$ algorithm for certain NP-complete problems](https://epubs.siam.org/doi/abs/10.1137/0210033), *SIAM Journal on Computing*, Vol. 10, Iss. 310, pp. 456–464.


