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$

closed as off-topic by MarcoB, LCarvalho, Alex Trounev, Öskå, José Antonio Díaz Navas Mar 21 at 19:51

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question arises due to a simple mistake such as a trivial syntax error, incorrect capitalization, spelling mistake, or other typographical error and is unlikely to help any future visitors, or else it is easily found in the documentation." – MarcoB, LCarvalho, Alex Trounev, Öskå, José Antonio Díaz Navas
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 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 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 at 5:26
  • $\begingroup$ @Somos I shall edit the question appropriately then. $\endgroup$ – TinyTim Feb 20 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 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.

$\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 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 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 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 at 6:06
  • 2
    $\begingroup$ Voted up already. You could also do FactorInteger[Range[n]]. $\endgroup$ – kglr Feb 20 at 8:28

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