Instead of iterating through all the possible numbers, is there a better way to find the greatest factor of a number $n$, such that it is less than $m$ ($m$ < $n$). Similarly how does one find the smallest factor of $n$ that is greater than $m$?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

You can certainly use Pollard's Rho algorithm to probabalistically compute the greatest factor of $n$ smaller than $m$ in $O(min(n^\frac{1}{4}, m^\frac{1}{2}) polylog(n))$ time. Your other question is actually the same as the first. That is $k>m$ is a factor of $n$ iff $\frac{n}{k}$ is a factor of $n$ and smaller than $\frac{n}{m}$. 


Here's a way to find small factors. I think that finding large factors (up to the square root of $n$) is as hard as factoring in general. Edit: Maybe the method in the paper I linked is not so great because it looks for small factors in a set of number. But it may cite more relevant papers. 

