2
$\begingroup$

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?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – J. M. is in limbo♦ May 22 '16 at 16:10
  • $\begingroup$ @J.M. I am not doing trial division, unless that's what IntegerExponent does. $\endgroup$ – rogerl May 22 '16 at 16:11
  • $\begingroup$ It looks equivalent to me, since you're only appending primes if they are factors of your number. $\endgroup$ – J. M. is in limbo♦ May 22 '16 at 16:13
  • $\begingroup$ @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. $\endgroup$ – rogerl May 22 '16 at 16:17
1
$\begingroup$

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}]]
|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.