3
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ 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.). $\endgroup$ – Noam D. Elkies Oct 28 '11 at 4:22
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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