# Efficiently create a list of factors of consecutive integers

I'm interested in a scalable (read: sublinear) algorithm for producing the list of integer factors of each integer from 1 to n. Note that I'm not necessarily asking about a sublinear factoring algorithm.

Using the built-in FactorInteger, I get the following timings for powers of ten up to 10^7:

Table[{j, First@Timing[Table[FactorInteger@i, {i, 1, 10^j}];]}, {j, 1, 7}]

(*{{1, 0.000039}, {2, 0.000255}, {3, 0.003083}, {4, 0.036405}, {5, 0.344576}, {6, 3.84674}, {7, 68.0302}}*)


This is more or less linear up through 10^6, but gets pretty bad at 10^7. One would think that it would be faster to build up a list of factorizations using the list of primes. Here is one attempt at doing so:

Table[{k, First@Timing[lim = 10^k;
lst = Table[{}, lim];
Do[AppendTo[lst[[i p]], {p, IntegerExponent[i p, p]}], {i, 1,
Floor[lim/p]}];
Do[addprime[Prime@p], {p, PrimePi[lim]}];]}, {k, 1, 7}]

(*{{1, 0.549175}, {2, 0.000767}, {3, 0.009434}, {4, 0.093252}, {5, 1.05787}, {6, 12.5425}, {7, 154.35}}*)


(For each prime, put the appropriate power of that prime at each slot in the results table.)

This is also close to linear, but consistently slower than the FactorInteger approach.

Perhaps I'm looking for something I can't have; the process of building up the required arrays may be inherently linear. Does anyone have better suggestions?

• Note that trial division will eventually become prohibitively expensive as your integers grow larger. FactorInteger[] supplements trial division with fanicer factoring methods (e.g. Pollard), so I'm pessimistic that you can outdo FactorInteger[] in this case. May 22, 2016 at 16:10
• @J.M. I am not doing trial division, unless that's what IntegerExponent does. May 22, 2016 at 16:11
• It looks equivalent to me, since you're only appending primes if they are factors of your number. May 22, 2016 at 16:13
• @J.M. Note that I'm not just trying to factor n; I'm generating a factor list for all integers below n. So while there might be something equivalent to trial division going on here, it is happening for all n integers at once. May 22, 2016 at 16:17

I have never been able to beat FactorInteger, but I was able to approximately double the speed of your code by using the following.

Block[{lim, v, r},
Table[{k,
First@AbsoluteTiming[
lim = 10^k;
v = ConstantArray[{}, lim];
Do[
r = p*Range[Floor[lim/p]];
v[[r]] = Join[v[[r]], Map[{{p, #}} &, IntegerExponent[r, p]], 2],
{p, Prime[Range[PrimePi[lim]]]}];
v]},
{k, 1, 7}]]