most recent 30 from http://mathoverflow.net 2013-05-21T15:55:45Z http://mathoverflow.net/feeds/question/79322 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79322/finding-the-greatest-smallest-factor-of-a-number-smaller-greater-than-another AG 2011-10-27T22:19:43Z 2012-02-17T07:22:12Z

<p>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$ &lt; $n$). Similarly how does one find the smallest factor of $n$ that is greater than $m$?</p>

http://mathoverflow.net/questions/79322/finding-the-greatest-smallest-factor-of-a-number-smaller-greater-than-another/79324#79324 psd 2011-10-27T22:25:41Z 2011-10-27T22:57:07Z

<p><a href="http://cr.yp.to/papers/sf.pdf" rel="nofollow">Here</a>'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.</p> <p>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.</p>

http://mathoverflow.net/questions/79322/finding-the-greatest-smallest-factor-of-a-number-smaller-greater-than-another/84136#84136 msg555 2011-12-23T03:34:13Z 2011-12-23T03:34:13Z

<p>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}$.</p>