The very efficient optimization in your code derived from Cristoforo's is this line: 
$x /= $y;

[download]
which replaces the target number by a number obtained by dividing the original number by any prime factor found. So, when you start to examine 600851475143, the code finds 71 as the first factor; so the problem is now reduced to looking for prime factors in the number 600851475143/71, i.e. 8462696833.

A bit later, the algorithm finds another prime factor 839, so that we are now left with 8462696833/839 = 10086647. And so on with the next factors, 1471 and 6857. This is very fast because the code finds very quickly prime factors which make it possible to considerably reduce the size of the problem.

But that huge optimization (BTW, this is, I believe, a variation on Euclid's algorithm for finding the GCD between two numbers) works only if you find prime factors relatively quickly. Even with a relatively modest prime number such as 2**31-1 (i.e. 2147483647) this program takes a very long time to run (well, more than 5 minutes instead of a split second): 

2 2 5
5 7 13 29
71 839 1471 6857
2147483647

real    5m44.346s
user    5m43.718s
sys     0m0.030s

[download]
(Note that I changed your code to display all the prime factors, rather than just the largest one.)

Now, if I am changing this code with three additional optimizations:

1. using only 2 and odd numbers as potential divisors,

2. looking for divisors only up to the square root of the target number (make sure you compute the square root only once for each for loop being executed);

3. starting the for loop with the largest prime factor already found;

then I get another huge improvement of your code (with the same input data). Instead of running in more than 5 minutes, this runs in 0.064 seconds: 

2 2 5
5 7 13 29
71 839 1471 6857
2147483647

real    0m0.064s
user    0m0.015s
sys     0m0.031s

[download]
Since this seems to be homework assignment, I will not disclose the code I have used for this test and leave it to you to try to implement the optimizations I described above.

In reply to Re^3: Avoid keeping larger lists in Memory by Laurent_R
in thread 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.