Re^8: Avoid keeping larger lists in Memory

Thanks Laurel . Have added another loop to check if the number is divisble by odd numbers and finally add to the number to the list oncethe number becomes greater than 2

#!/usr/bin/perl
use warnings;
use strict;
########

sub prime_factors {
    my $num = shift;
    my @primes = ();
    my $max = sqrt($num);
    while ($num % 2 == 0) {
        push @primes, 2;
        $num /= 2;
    }

    foreach (my $i = 3; $i <= $max; $i += 2) {
        if ($num % $i == 0) {
            push @primes, $i;
            $num /= $i;
                $max = sqrt($num);
             redo;
        }
     }

     if ($num > 2) {
        push @primes, $num;
     }

     return @primes;
}

foreach my $n ( (20, 48, 96, 7, 69, 33, 54, 13195,  600851475143, 2147
+483647, 29474100, 3217491003, 27000) ) {
    my @result = prime_factors($n);
    print "Number: $n , Prime_Factors: => @result", "\n";
}

$time ./primes.pl
Number: 20 , Prime_Factors: => 2 2 5
Number: 48 , Prime_Factors: => 2 2 2 2 3
Number: 96 , Prime_Factors: => 2 2 2 2 2 3
Number: 7 , Prime_Factors: => 7
Number: 69 , Prime_Factors: => 3 23
Number: 33 , Prime_Factors: => 3 11
Number: 54 , Prime_Factors: => 2 3 3 3
Number: 13195 , Prime_Factors: => 5 7 13 29
Number: 600851475143 , Prime_Factors: => 71 839 1471 6857
Number: 2147483647 , Prime_Factors: => 2147483647
Number: 29474100 , Prime_Factors: => 2 2 3 3 5 5 32749
Number: 3217491003 , Prime_Factors: => 3 32749 32749
Number: 27000 , Prime_Factors: => 2 2 2 3 3 3 5 5 5

real    0m0.015s
user    0m0.009s
sys    0m0.004s
[download]

Comment on Re^8: Avoid keeping larger lists in Memory Download Code

Replies are listed 'Best First'.
Re^9: Avoid keeping larger lists in Memory by Laurent_R (Canon) on Jul 05, 2017 at 06:25 UTC
This is pretty good, you captured, I believe, most of the recommended optimizations. In the beginning of your program, for better efficiency, you should have this line: `my $max = sqrt($num);` [download] after the while loop, so that you better benefit from the size reduction associated with the elimination of the powers of two from the original target number. In the foreach loop, you could recalculate $max immediately after having modified $num (this will be efficient for some input data, such as the product of two or a few large primes), but, for safety, you would need to restart the foreach loop with a redo. Actually, it would be easier, clearer and safer to rewrite this loop as a while loop.	[reply] [d/l]
Re^9: Avoid keeping larger lists in Memory by pryrt (Abbot) on Jul 05, 2017 at 14:12 UTC
adding to your list of test cases: `foreach my $n ( @ARGV ? @ARGV : (20, 48, 96, 7, 69, 33, 13195, 600851 +475143, 2147483647) ) {` [download] ... 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` [download] 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: <Reveal this spoiler or all in this thread> $ 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 [download] 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% --` [download]	[reply] [d/l] [select]
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.	[reply]