4
$\begingroup$

Is there a neat way to find the largest integer that divides another integer fully, within a range. As an example, I would like to find the largest integer smaller than 1131 that divides 3500 completely.

So far I have just tried by breaking up 3500 into its prime components and guessing, coming to 875, but is there a more structured way?

EDIT: I guess the problem is somewhat equivalent to get all dividing integers, and then just pick the largest within my range?

$\endgroup$
1
  • $\begingroup$ Sounds like you already know this, but knowing $3500=2^2\cdot 5^3\cdot 7$, there are $3\cdot4\cdot 2=24$ divisors. In this case you can just list all divisors, intersect that with $[1,1131]$, and take the max. Its not guaranteed to be efficient but its at least rigorous. $\endgroup$ Commented Jan 8, 2017 at 1:28

2 Answers 2

Reset to default
2
$\begingroup$

You could look for the smallest integer greater than $\dfrac{3500}{1131}\approx 3.09$ that divides $3500$ exactly

This is obviously $4$ (there is no smaller integer greater then $3.09$ and $4$ does divide $3500$ as it divides $100$) so the answer to your original question is $\dfrac{3500}{4}=875$

$\endgroup$
1
$\begingroup$

There is a randomized reduction from SUBSET-SUM to this problem, and it is NP-complete assuming a weak version of Cramér's conjecture. So there is no neat general solution, but of course there are many special cases that can be determined quickly (for example if the suspected multiple is prime we can test that in polynomial time and know that there is no divisor in the range, or if the range is small enough that the divisibility by each member can be tested individually).

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.