MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

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