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$?

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. 


I think this may be an NPhard problem similar to knapsack problem. It's straightforward to translate it into an instance of knapsack problem: let the knapsack size be $\log m$ and the items be $\log p_i$, where $p_i$ are prime factors of $n$. In order to prove NPhardness one has to translate a general knapsack problem instance to this one though. 

