in reply to Re^8: Avoid keeping larger lists in Memory
in thread Avoid keeping larger lists in Memory

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% --

Replies are listed 'Best First'.
Re^10: Avoid keeping larger lists in Memory
by pr33 (Scribe) on Jul 05, 2017 at 17:44 UTC

    Thanks pryt. I fixed the problem with for loop by dividing it with only prime factors in the previous thread . Also the execution time has improved upon calculating the square root every time after changing the value of num in the for loop.