Re: The prime factors of n.
- To: mathgroup at smc.vnet.net
- Subject: [mg32719] Re: [mg32673] The prime factors of n.
- From: Sseziwa Mukasa <mukasa at jeol.com>
- Date: Thu, 7 Feb 2002 05:10:04 -0500 (EST)
- Organization: JEOL (USA) Ltd.
- References: <200202060841.DAA02157@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
"Robert G. Wilson v" wrote:
> Hello all,
>
> I wish to receive a list of prime factors of n not in the form
> returned by FactorInteger. Instead I want only the primes the number of
> times they appear. As an example I will use 72. FactorInteger[72] gives
> { {2,3}, {3,2} }. I wish the list would read { 2, 2, 2, 3, 3 }. Is the
> following the best that I can do? f[n_Integer] := Module[{a =
> FactorInteger[n], b = {}}, While[Length[a] > 0, Do[b = Append[b, a[[1,
> 1]]], {a[[1, 2]]}]; a = Drop[a, 1]]; b] .
>
> See
> http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=037276
>
> Sincerely yours,
>
> Robert G. "Bob" Wilson, V
The while and do loops are not necessary and all the assignments and modifications of
variables probably slow your function down here's another approach:
Option 1:
f[n_Integer]:=(Sequence@@Table[#[[1]],{#[[2]]}])&/@FactorInteger[n]
you can also use
Option 2:
f[n_Integer]:Flatten[Table[#[[1]],{#[[2]]}]&/@FactorInteger[n]]
Since you're working on lists of factors FactorInteger will dominate the amount of time
the function takes anyways and the resulting lists will probably not be very large. But
comparing the performance of your function versus the other options on a list of pairs
Table[{1,Random[Integer,{1,5}]},{10000}] provides the following results (I removed the
FactorInteger and made the argument a list): your method takes 2.4 seconds, option 1
takes 0.65 seconds and option 2 takes 0.48 seconds.
Regards,
Sseziwa Mukasa
- References:
- The prime factors of n.
- From: "Robert G. Wilson v" <rgwv@kspaint.com>
- The prime factors of n.