MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
This can be hard even if $n$ is squarefree with known but numerous prime factors, because it reduces to a knapsack problem (given items of size $c_i$, find $s$ large enough to approximate $\exp sc_i$ sufficiently well by primes $p_i$, and take $n = \prod_i \phantom. p_i$, etc.). – Noam D. Elkies Oct 28 '11 at 4:22

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

share|cite|improve this answer

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.

share|cite|improve this answer

I think this may be an NP-hard 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 NP-hardness one has to translate a general knapsack problem instance to this one though.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.