Hello Monks,

I have a program to find the largest prime factor for a given number . If the given number is small, The execution time is fast. For Large number though, My program just hangs . My machine has a total of 16GB Physical RAM . Wanted to find if there is an alternative way to keep larger lists in memory or avoid it by reading the value and throwing it after returning the result . Below is my code 

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

sub is_prime {
    my $num = shift;
    my $x = 2;
    my $on = 0;
    while ($num > $x) {
      if ( $num % $x == 0 ) {
          $on = 1;
          last;
        }
     $x++;
   }
    return 'False' if $num <= 2;
    if ($num > 2) {
        if (! $on) {
         return 'True';
        }elsif($on) {
          return 'False';
        }
     }
}

sub largest_prime_factor {
    my $i = 2;
    my $num = shift;
    my $large_prime = 0;
    my $prime_factors = [];
    my $factors = [];
    while ($i <= $num - 1) {
     if ($num % $i == 0 ) {
         push @$factors, $i;
     }
     $i++;
  }

   $i = 0;
   while ( $i <= scalar(@$factors) - 1) {
    my $a = is_prime($factors->[$i]);
    if ($a eq 'True') {
          push @$prime_factors, $factors->[$i];
    }
     $i++;
  }

   $i = 0;

   while ($i <= scalar(@$prime_factors) - 1) {
    if ($prime_factors->[$i]  > $large_prime) {
        $large_prime = $prime_factors->[$i];
    }
    $i++;
  }

   return $large_prime;

}

print largest_prime_factor(20), "\n";
print largest_prime_factor(13195), "\n";
print largest_prime_factor(600851475143), "\n";

[download]

Results:

$./large_prime_factor.pl
5
29

[download]

In reply to Avoid keeping larger lists in Memory by pr33

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.