A faster Divisors function
- To: mathgroup at smc.vnet.net
- Subject: [mg22890] A faster Divisors function
- From: Julian Aguirre Estibalez <mtpagesj at lg.ehu.es>
- Date: Tue, 4 Apr 2000 22:40:58 -0400 (EDT)
- Organization: Universidad del Pais Vasco/Euskal Herriko Unibertsitatea
- Sender: owner-wri-mathgroup at wolfram.com
Dear group,
I need to find the divisors of a large collection of integers, all
of them having small prime factors. An example is
In[22]:= n = 5910740121125371424569009155900;
Mathematica factorizes it without problems:
In[23]:= FactorInteger[n] // Timing
Out[23]=
{0. Second, {{2, 2}, {3, 2}, {5, 2}, {7, 2}, {11, 1}, {23, 1}, {37, 1},
{79, 1}, {179, 1}, {191, 1}, {223, 1}, {239, 1}, {269, 1}, {419, 1},
{457, 1}, {1931, 1}}}
But when trying to compute Divisors[n], I stopped the calculation
after one hour. I have written my own divisors function:
MyDivisors[n_Integer]:=With[{f=FactorInteger[n]},
Sort at Fold[Flatten@Outer[Times, #1, #2]&, {1}, First/@f^Range[0, Last/@f]]]
In[32]:=Length at MyDivisors[n] // Timing
Out[32]={16.7333 Second, 331776}
As you can see, it is fast, but uses a lot of memory. Of course,
it works well with numbers that can be easily factorized, which is always
the case with the problem I am working in. Now my question. Can any of you
suggest a better way of improving the speed or diminishing the memory
rquirements of MyDivisors?
Thanks,
Julian Aguirre | Voice: +34 946012659
Departamento de Matematicas | Fax: +34 944648500
Universidad del Pais Vasco | Postal: Aptdo. 644, 48080 Bilbao, Spain
| email: mtpagesj at lg.ehu.es
- Follow-Ups:
- Re: A faster Divisors function
- From: Hartmut Wolf <hwolf@debis.com>
- Re: A faster Divisors function