Algorithm for finding integers in a range with multiples in a short interval

Question

Is there a quick way to determine which integers $D < d\leqslant 2D$ are such that $d$ has a multiple in $[X, X + H]$? Here, $H$ should be thought of as much smaller than $D$, and $X$ larger than $D$. It is easy to find this in time linear in $D$ by just checking for some $d$ if $\lfloor X/d\rfloor\ne \lfloor (X + H)/d\rfloor$. Is there any way to do better, perhaps through some structure those $d$s that do have such a multiple must satisfy ?

Answer 1

Depending on the value of $D$ as compared to $X$, you may want to switch from scanning the interval $[D+1,2D]$ to the interval of co-factors: $\big[ \lceil \frac{X}{2D} \rceil, \lfloor \frac{X+H}{D+1}\rfloor \big]$.

Alternatively, you can just try to factor each number in the interval $[X,X+H]$ as suggested in the comments and directly find their divisors in the interval $[D+1,2D]$, or employ particular techniques used for the integer factorization such as sieving. For example, if one finds that a prime $p$ does not divide any integer in the interval $[X,X+H]$, then multiples $p$ can be excluded from the candidates in $[D+1,2D]$.