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];
addprime[p_] :=
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?
FactorInteger[]
supplements trial division with fanicer factoring methods (e.g. Pollard), so I'm pessimistic that you can outdoFactorInteger[]
in this case. $\endgroup$ – J. M.'s ennui♦ May 22 '16 at 16:10n
; I'm generating a factor list for all integers belown
. So while there might be something equivalent to trial division going on here, it is happening for all n integers at once. $\endgroup$ – rogerl May 22 '16 at 16:17