I'm implementing the Cooley-Tukey algorithm for computing Discrete Fourier transforms. It so happens that it breaks down a problem of size $n = pq$ into $p$ chunks of size $q$.
Given that factoring of a random integer is (classically) hard, many simply pad the input with zeros so that the problem size is rounded up to a power of 2, and I wonder if we can do better.
Is there an algorithm that for $n$, outputs $(p,q)$, not necessarily prime, such that $n \leq pq \leq cn$ with $c$ significantly less than 2, and does so in a time polynomial in $log(n)$?
Find the two lowest primes $\ge \sqrt{n}.$ This is not $O(\log n),$ but maybe fast enough for your purpose?
It is also comforting to know that for any $n \ge 468991632$ there is at least one prime between $n$ and $(1 + 1/(5000 \ln^2(x)))x.$ See 'Explicit estimates of some functions over primes' by Pierre Dusart in the Ramanujan Journal (https://link.springer.com/article/10.1007/s11139-016-9839-4).