Finding divisors of an interval of integers This numerical problem arose in one of my projects. It seems simple at first sight, but I can't seem to find a good approach. Maybe someone else has an idea:

We have two integers, $n$ and $N$. Let's say that $n \approx 10^6$ and $N>10^{18}$.

I need to create a list of all numbers between n and $\sqrt N$ that divide some number in the interval $[N,N+n-1]$.

Obviously, each number can divide at most one, and the total number of answers is approximately $n \ln{\sqrt N  \over n}$; $6.9*10^6$ for $10^{18}$.

The most straightforward approach is to enumerate all integers from $n$ to $\sqrt N$ and to try each one, and that takes $O(\sqrt N)$ operations. Surely we can do much better?
Your problem is more or less equivalent to the problem of factoring $N,N+1,\ldots,N+n$. To get from these factorizations to the solution to your problem, simply enumerate the factors. To get from the solution to your problem to the factorization, simply test each factor for primality. In the future you may wish to state this problem in this other form, as it sounds more natural and fundamental that way.

One way to factor these numbers is to simply use a standard factorization algorithm on each one. Note that most numbers have lots of small divisors and therefore are a lot easier to factor than the products of two large primes that need to be factored to break RSA public key cryptography. According to Wikipedia the Lenstra elliptic curve factorization method works well on numbers with small factors and the Quadratic Sieve works well for numbers under 100 digits. I would give those two factorization algorithms a try.

In light of the above I suggest something along the lines of the following algorithm:

Iterate over all numbers X between $N$ and $N+n$. For each such X:


Compute its prime factors as follows:

i. Use trial division by 2,3,5 and 7 to dispose of tiny factors

ii. Run the Lenstra or Quadratic Sieve factorization method to factor what's left.
Use the prime factorization to generate all factors (prime or composite) of X. Insert all of these factors that are between $n$ and $\sqrt{N}$ to your output list.