2
$\begingroup$

For a problem I am working on, I need to create sets all the prime factors of a large set of integers (at least on the order of 1$-$1,000,000 but more on the order of all integers 1 to $10^{12}$). Factor integer would most likely work too slowly in Mathematica (it seems to). Faster would most likely to be create the set of integers of 1 to $N$ directly, so one would a priori have the prime factorization.

My rough approach is as follows (one can obviously keep track of factors, so I only am concerned here with constructing the $n$'s): First, construct all the primes up to $N$.

construct[N_]:= Module[{},
   primes = {};
   k = 1;
   While[ Prime[k] <= N, AppendTo[ primes, Prime[k] ];
   numbers = primes;

Now you have to work with the set of primes only up to $N/2$ as factors of non-prime numbers up to $N$. So I restrict the set of primes.

construct[N_]:= Module[{},
   primes = {};
   k = 1;
   While[ Prime[k] <= N, AppendTo[ primes, Prime[k] ];
   numbers = primes;
   k = 1;
   While[ primes[[k]] <= N/2, k++];
   primes = Take[ primes, k-1];

But now one needs to loop through all products of all powers of elements from 'primes'. For instance, if $N = 15$, we have primes $=\{ 2,3,5,7\}$. Then we need to append to 'numbers' all numbers of the form $2^i3^j5^k7^l$, for all $i,j,k,l$ such that the product is at most $15$. Creating a condition on $i,j,k,l$ arbitrarily is simple, so one would only need to consider $1 \leq i,j,k,l \leq M$ for some fixed $M$, even for a general collection of powers, but how does one tell Mathematica to loop through all these possible powers, especially since the number of primes one will need to consider will depend on $N$?

$\endgroup$
  • 3
    $\begingroup$ This question may stem from an XY problem, I.e. you are asking about your attempted solution, rather than about your actual problem. This is underlined by your use of very un-idiomatic MMA code (lots of while loops, AppendTo, etc). Perhaps you could ask about the actual problem you are trying to solve instead. $\endgroup$ – MarcoB Feb 20 '19 at 5:00
  • $\begingroup$ @MarcoB Minus the fact that I will then eventually sift through the set, this is the problem I am working on. Yes, one could just create a set of 1 to $N$, but I will need the factors for very large $N$ and it should be faster to create the integers rather than create the set and then factor each and every $N$. I would certainly appreciate any feedback - I am a mathematician not a programmer, so I program in a way that makes mathematical sense to me - not in a CS coherent way. $\endgroup$ – TinyTim Feb 20 '19 at 5:17
  • $\begingroup$ @Somos Depending on how Mathematica ends up handling the task, at least every integer from 1 to 100 million, and possible something more on the order of $10^{12}$. $\endgroup$ – TinyTim Feb 20 '19 at 5:26
  • $\begingroup$ @Somos I shall edit the question appropriately then. $\endgroup$ – TinyTim Feb 20 '19 at 5:30
  • 2
    $\begingroup$ You still won't have the RAM to store it though no matter how fast you compute it. Try Range[10^12] for example. $\endgroup$ – Somos Feb 20 '19 at 5:44
6
$\begingroup$

In Mathematica the code to solve your problem is trivial. Like so:

With[{n = 15}, Table[FactorInteger[i], {i, n}]]

which gives

{{{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 2}}, {{5, 1}}, {{2, 1}, {3, 1}}, {{7, 1}}, 
 {{2, 3}}, {{3, 2}}, {{2, 1}, {5, 1}}, {{11, 1}}, {{2, 2}, {3, 1}}, {{13, 1}}, 
 {{2, 1}, {7, 1}}, {{3, 1}, {5, 1}}}

I doubt if any looping code you might write will beat this.

| improve this answer | |
$\endgroup$
  • $\begingroup$ As requested in the comments to the question, my goal is to do this for very large $N$. Will factor integer still be the faster approach if one needs to do this for all integers from $1$ to, say, $10^{12}$? $\endgroup$ – TinyTim Feb 20 '19 at 5:36
  • 1
    $\begingroup$ @TinyTim. The problem with` n = 10^12` is running out of memory. That would be just as true for any custom procedural code you might write than as for my code. For such big sequences of numbers, considerations of breaking the calculation in blocks and pushing completed block out to file storage will overwhelm the factorization part of the code. FactorInteger is very fast; on my system, it factors 10^2 in less than 4 μ-sec. $\endgroup$ – m_goldberg Feb 20 '19 at 5:55
  • $\begingroup$ Alright, I will stick to my original use of FactorInteger and worry about the memory issue later. Thanks for the information! $\endgroup$ – TinyTim Feb 20 '19 at 5:58
  • $\begingroup$ @TinyTim, Correction to my previous comment: FactorInteger is very fast; on my system, it factors 10^12 in less than 4 μ-sec $\endgroup$ – m_goldberg Feb 20 '19 at 6:06
  • 2
    $\begingroup$ Voted up already. You could also do FactorInteger[Range[n]]. $\endgroup$ – kglr Feb 20 '19 at 8:28

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