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

```

• Prev by Date: Re: Re: Counting the total number of available Mathematica commands ?
• Next by Date: Re: 9^(9^(9^9))
• Previous by thread: Re: Re: 3 credit online university course - Intro to Mathematica
• Next by thread: Re: A faster Divisors function