Factoring blocks of numbers Asked this question in a different formulation in cstheory, got some pointers, but no definitive answer ... maybe someone here knows.
Suppose I need to compute the factorization of a block of consecutive numbers N, N+1, ... N+n. 
As far as I understand, there are two extreme cases. On one hand, if n is very small, I can use algorithms for isolated numbers such as the quadratic sieve. Those are very nice because they make factorizations of 100-digit numbers tractable, but they have limited usefulness for smaller N's (for example, the complexity of the quadratic sieve for N=10^15 comes out to 60,000 operations).
If $n>\sqrt{N}$, I can compute primes up to $\sqrt{N}$ and then factorize the whole block directly in O(n) time.
In between these two extremes, isolated integer factorization methods are slow due to a big fat constant, and direct factorization is slow because it has a minimum running time of $O(\pi(\sqrt{N})) = \sqrt{N} / \ln \sqrt{N}$. 
Is there any algorithm that will get me a better running time in this region? We can assume that I have all the prime numbers up to $\sqrt{N}$ computed and stored so the time to compute them does not have to be included.
 A: Short answer: I doubt you can do much better than trial factorization.  However, for many
composite numbers, the run time is often up to the size of the second largest prime factor,
so you may actually end up with a better run time than pi(sqrt(N)).
Long answer: there are lots of things to try.  First is to remove the small factors,
of which you know there will be many.  Assuming you have them, start removing all factors
up to, say q = pi(n), the nth prime.  (You can even try it recursively, as e.g. the
even members of your sequence are twice a consecutive run of numbers.)
 You will have left an array of n numbers, many of
which are prime or have few factors.  If they are less than q^2, then they will be
prime or 1, and those numbers can be considered to be completely factored.
With the remaining numbers, a fact you know is that each pair is relatively prime.  One fun thing to try is to multiply an odd number of them that are about the same size
together and then try Fermat's difference of squares method on the result.  If you
choose few enough of them, you can find a number which has a nontrivial factor in
common with one of the numbers in the product.
Another thing you can do is take a random selection of primes s in (q, sqrt(N)) and compute N mod s.
If the result is between -n and 0, then exactly one of the array has s as a factor.
After enough trials of these, you can try high-powered methods on the rest, or even
on products of the rest.
Gerhard "Ask Me About System Design" Paseman, 2010.10.10
A: Using a sieve of Eratosthenes approach, it is easy to create a list $S$ of the smallest prime factor of every number less than $N$. Then to factor any $n < N$, we just recursively look up the factors: let $n_1=n$, $f_i = S(n_i)$, and $n_{i+1} = n_i/f_i$.  With 4 GB of memory, numbers less than ${10}^9$ are quickly factored. Although this algorithm takes more memory, it is much faster than trial division.
A: Daniel Bernstein has a method of finding smooth numbers in batches.  See http://cr.yp.to/papers/sf.pdf.
