<p>Your problem is more or less equivalent to the problem of factoring <span class="math-container">$N,N+1,\ldots,N+n$</span>. 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.</p>
<p>One way to factor these numbers is to simply use a standard factorization algorithm on each one. Note that most numbers have <a href="https://doi.org/10.1007/BF01817702" rel="nofollow noreferrer" title="Erdős, P. On the distribution of prime divisors. Aeq. Math. 2, 177–183 (1969)">lots of small divisors</a> 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 <a href="https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization" rel="nofollow noreferrer">Lenstra elliptic curve factorization method</a> works well on numbers with small factors and the <a href="https://en.wikipedia.org/wiki/Quadratic_sieve" rel="nofollow noreferrer">Quadratic Sieve</a> works well for numbers under 100 digits. I would give those two factorization algorithms a try.</p>
<p>In light of the above I suggest something along the lines of the following algorithm:</p>
<p>Iterate over all numbers X between <span class="math-container">$N$</span> and <span class="math-container">$N+n$</span>. For each such X:</p>
<ol>
<li><p>Compute its prime factors as follows:</p>
<p>i. Use trial division by 2, 3, 5 and 7 to dispose of tiny factors</p>
<p>ii. Run the Lenstra or Quadratic Sieve factorization method to factor what's left.</p>
</li>
<li><p>Use the prime factorization to generate all factors (prime or composite) of X. Insert all of these factors that are between <span class="math-container">$n$</span> and <span class="math-container">$\sqrt{N}$</span> to your output list.</p>
</li>
</ol>

CC BY-SA 2.5
2010-10-09T20:07:31.543Z
That is an intriguing approach, but I have doubts about the running time. As far as I understand, Lenstra gives me the one prime factor per invocation. The complexity of quadratic sieve works out to ~600 operations for N~10^18. Worth a try though.
user1703
CC BY-SA 2.5
2010-10-10T00:55:50.410Z
Here's another suggestion: build a table with the current known prime factors of $N,\ldots,N+n$, initialized to empty. Then for every prime $p<n$, update this table to account for divisibility by $p$. This process finds each prime factor using $O(1)$ arithmetic operations. I suggest stopping at $p\approx n$ because larger primes need not divide any number in the range $N,\ldots,N+n$. This preliminary step will find an awful lot of factors, leaving the quadratic sieve with much smaller numbers to factor.
Warren Schudy
CC BY-SA 2.5
2010-10-10T02:12:03.977Z
You should of course use a primality test (e.g. Rabin-Miller) to verify compositeness before trying to factor a number.
Warren Schudy
CC BY-SA 2.5
2010-10-10T14:32:52.003Z
Correction: A random number between $M^2$ and $4M^2$ is a product of two primes between $M$ and $2M$ with probability $\Theta(\frac{1}{(\log M)^2})$, which follows easily from the distribution of primes (http://en.wikipedia.org/wiki/Prime_number_theorem) and the uniqueness of prime factorizations. This implies that tricks to get rid of smaller factors don't significantly help the asymptotic performance.
Warren Schudy
CC BY-SA 2.5
2010-10-10T14:33:25.307Z
The quadratic sieve factoring algorithm takes time $o(N^\epsilon)$ for every $\epsilon>0$, so factoring all of the numbers can be done in time $O(n N^\epsilon)$. Unless $n$ is close to $\sqrt{N}$ this is still faster than your naive method.
Warren Schudy
CC BY-SA 2.5
2010-10-11T00:00:34.887Z
Ok, I made a miscalculation. Quadratic sieve takes O(exp[sqrt(ln N) sqrt(ln ln N)]) time. That's 250,000 times some constant for N=10^18. Assuming that the constant is small, the quadratic sieve will start coming ahead of the naive method for N>~10^26.
user1703
CC BY-SA 4.0
2010-10-09T17:41:52.493Z
2022-11-14T12:38:35.267Z
2022-11-14T12:38:35.267Z
Warren Schudy
<p>You might as well list all numbers from 1 to $\sqrt{N}$. Then the problem is more or less the same as finding all prime factors of all numbers in an interval. Using the Sieve of Atkin to generate primes you can get $ O(\sqrt{N}/\log \log N) $.</p>

CC BY-SA 2.5
2010-10-09T14:14:14.790Z
2010-10-09T14:14:14.790Z
Colin McQuillan
<p>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:</p>

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

<p>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]$.</p>

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

<p>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?</p>

CC BY-SA 2.5
2010-10-09T20:12:30.783Z
I've been able to derive a formula that gives me approximate locations of some divisors: $q+(k-\sqrt{4*q*k-k^2})/2$ where $q=\sqrt{N}$ and k is a small integer (assuming that N is a perfect square). But that does not generalize well enough ...
user1703
CC BY-SA 2.5
2010-10-11T20:48:22.590Z
Now it is crossposted on MathOverflow with a little different formulation (I presume that the poster is the same person): http://mathoverflow.net/questions/41725/factoring-blocks-of-numbers
Tsuyoshi Ito
<ds.algorithms><nt.number-theory>
Finding divisors of an interval of integers
user1703
# Finding divisors of an interval of integers

(Asked by: username_0 on 2010-10-09)

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?

**Tags:** ds.algorithms, nt.number-theory

> **Comments:**
> **username_0**: I've been able to derive a formula that gives me approximate locations of some divisors: $q+(k-\sqrt{4*q*k-k^2})/2$ where $q=\sqrt{N}$ and k is a small integer (assuming that N is a perfect square). But that does not generalize well enough ...  
> **username_1**: Now it is crossposted on MathOverflow with a little different formulation (I presume that the poster is the same person): http://mathoverflow.net/questions/41725/factoring-blocks-of-numbers  

---

## 2 answers

### Answer by username_2 on 2010-10-09. Score: 2 | Accepted answer

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](https://doi.org/10.1007/BF01817702 "Erdős, P. On the distribution of prime divisors. Aeq. Math. 2, 177–183 (1969)") 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](https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization) works well on numbers with small factors and the [Quadratic Sieve](https://en.wikipedia.org/wiki/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:

1. 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.
2. 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.

> **Comments:**
> **username_0**: That is an intriguing approach, but I have doubts about the running time. As far as I understand, Lenstra gives me the one prime factor per invocation. The complexity of quadratic sieve works out to ~600 operations for N~10^18. Worth a try though.  
> **username_2**: Here's another suggestion: build a table with the current known prime factors of $N,\ldots,N+n$, initialized to empty. Then for every prime $p<n$, update this table to account for divisibility by $p$. This process finds each prime factor using $O(1)$ arithmetic operations. I suggest stopping at $p\approx n$ because larger primes need not divide any number in the range $N,\ldots,N+n$. This preliminary step will find an awful lot of factors, leaving the quadratic sieve with much smaller numbers to factor.  
> **username_2**: You should of course use a primality test (e.g. Rabin-Miller) to verify compositeness before trying to factor a number.  
> **username_2**: Correction: A random number between $M^2$ and $4M^2$ is a product of two primes between $M$ and $2M$ with probability $\Theta(\frac{1}{(\log M)^2})$, which follows easily from the distribution of primes (http://en.wikipedia.org/wiki/Prime_number_theorem) and the uniqueness of prime factorizations. This implies that tricks to get rid of smaller factors don't significantly help the asymptotic performance.  
> **username_2**: The quadratic sieve factoring algorithm takes time $o(N^\epsilon)$ for every $\epsilon>0$, so factoring all of the numbers can be done in time $O(n N^\epsilon)$. Unless $n$ is close to $\sqrt{N}$ this is still faster than your naive method.  
> **username_0**: Ok, I made a miscalculation. Quadratic sieve takes O(exp[sqrt(ln N) sqrt(ln ln N)]) time. That's 250,000 times some constant for N=10^18. Assuming that the constant is small, the quadratic sieve will start coming ahead of the naive method for N>~10^26.  

---

### Answer by username_3 on 2010-10-09. Score: 0

You might as well list all numbers from 1 to $\sqrt{N}$. Then the problem is more or less the same as finding all prime factors of all numbers in an interval. Using the Sieve of Atkin to generate primes you can get $ O(\sqrt{N}/\log \log N) $.


---

