adding to your list of test cases:
foreach my $n ( @ARGV ? @ARGV : (20, 48, 96, 7, 69, 33, 13195, 600851 +475143, 2147483647) ) {
... and running with some different test cases, I get
perl pm1194192.pl 18 54 27000 29474100 Number: 18 , Prime_Factors: => 2 3 3 Number: 54 , Prime_Factors: => 2 3 9 Number: 27000 , Prime_Factors: => 2 2 2 3 5 9 25 Number: 29474100 , Prime_Factors: => 2 2 3 5 15 32749
That's not right for all cases -- any that happen to have more than one instance of a non-two prime. 18 sneaked by, because of the way the error works, but it becomes obviously wrong for 54: 9 is not prime, and should have been eliminated during the $i=3 iteration. In 27000, 9 and 25 are both non-prime. The redo in the example code in Cristoforo's post handled multiple instances of the same prime factor, but your for loop does not
If I change the next to redo, it fixes that problem. And if I take the root after every recalculation of $num, it becomes somewhat more efficient:
$ time perl pm1194192.pl 18 54 27000 29474100 3217491003 Number: 18 , Prime_Factors: => 2 3 3 Number: 54 , Prime_Factors: => 2 3 3 3 Number: 27000 , Prime_Factors: => 2 2 2 3 3 3 5 5 5 Number: 29474100 , Prime_Factors: => 2 2 3 3 5 5 32749 Number: 3217491003 , Prime_Factors: => 3 32749 32749 real 0m0.010s user 0m0.008s sys 0m0.000s $ time perl pm1194192.pl --sqrt 18 54 27000 29474100 3217491003 Number: 18 , Prime_Factors: => 2 3 3 Number: 54 , Prime_Factors: => 2 3 3 3 Number: 27000 , Prime_Factors: => 2 2 2 3 3 3 5 5 5 Number: 29474100 , Prime_Factors: => 2 2 3 3 5 5 32749 Number: 3217491003 , Prime_Factors: => 3 32749 32749 real 0m0.008s user 0m0.004s sys 0m0.000s
When I'd run without --sqrt, I'd consistently get real times of 10-15ms and user times of 8-12ms. With --sqrt, I consistently got real 7-9 and user of 4ms.
For fixing the multiple of the same prime factor problem, instead of using redo, you could also change if ($num % $i == 0) { to while ($num % $i == 0) { (and my sqrt mod would still work as advertised)
update: or, with proper Benchmarking of two different copies of the function (prime_factors() without the per-loop sqrt, and prime_factors_sqrt() with per-loop sqrt):
... my @list = (20, 48, 96, 7, 69, 33, 13195, 600851475143, 2147483647, 1 +8, 54, 27000, 29474100, 589806); foreach my $n ( @list ) { my @result = prime_factors($n); print "Number: $n , Prime_Factors: => @result", "\n"; } use Benchmark qw(cmpthese); cmpthese( -10, { once => sub { prime_factors($_) for @list }, every => sub { prime_factors_sqrt($_) for @list }, }); __END__ ... Rate once every once 16.9/s -- -94% every 286/s 1593% --
In reply to Re^9: Avoid keeping larger lists in Memory
by pryrt
in thread Avoid keeping larger lists in Memory
by pr33
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |