in the latest version of pr33's code, the variable name is $num. So yes, I think the sqrt should be recalculated each time $num changes. In the code I had tested and bench marked earlier based on the previous version of the code proposed by pr33, the variable name was $x. And, yes, I recalculated the sqrt of $x each time $x was recalculated, but I avoided to do it within the header of the for loop, to avoid recalculating it at each iteration of the loop. In other words, I was sort of caching the value of the sqrt. This made the code a bit more complicated, but also quite faster

The latest version of pr33's code does not have a redo and is changing the loop variables within the loop, which might possibly work but is probably a bit dangerous with possible side effects. Restarting the loop with a redo is certainly less error prone.

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]

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.

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]