I want to factorize big numbers like 10^100. FactorInteger
with no Automatic
option can take a lot of time and as I know there is no way to show any progress. So I tried to make a custom function that ends in a short time and will return some result that can be used in future runs. For now I have this one:
FirstFactors[n_Integer, k_Integer, start_Integer : 1] :=
Module[
{p, lastP, factors, m, i},
Monitor[
p = NextPrime[start]; lastP = p; factors = {}; m = n; i = 0;
Do[
If[
PrimeQ[m], factors = Append[factors, m]; m = 1; Break[],
lastP = p;
If[Mod[m, p] == 0, factors = Append[factors, p]; m = m/p,
p = NextPrime[p]]
]; i++,
k
];
{factors, m, p},
Grid[{{ProgressIndicator[i/k], ToString[N[i/k*100, 3]] <> "%"}}]
]
]
It implements simple algorithm and it work slooooowly. But I can run it for 10^6 steps and it will take about a minute (after 10^9 steps it will be more than mimute for next 10^6 steps). Then I can run it for 10^6 steps more and start from last checked prime.
There are two main problems:
- This algorithm can not be parallelized in simple way
- The algorithm itself has too big computational complexity
Any ideas to improve my solution? I need a function that will work for any number, so some methods (i.e. Pollard's p − 1) are not appropriate because they can find only factors having specific form.
FactorInteger
with simple trial division algorithm :-D $\endgroup$