The problem you are coming across isn't Perl, it's your algorithm. Learning algorithms is great -- and there have been recent discussions on algorithms for Primes (use Super Search to look for "Prime") -- but is that what you want to spend your time on right now?
Given your stated goal of learning about Perl and how to make modules, I'd just go down that path with your current algorithm, and just not test or debug it on large prime_candidates to avoid long times.
If you still want to focus on the algorithm, great; here are a few brief comments on your algorithm:
- Despite your assertion, it won't find all non-primes in a flash; if a non-prime has a very large number as its lowest prime factor, then it will take a long time to get that far
- You are testing at least 2x as many divisors as you need to: except for 2, there are no even primes, so don't include those in your loop: foreach my $each_num ( 2, map { 2*$_+1 } 1 .. $prime_candidate/2) -- see perldoc -f map for how map works
- If you also think about odd multiples of 3, that's still too many; other than 3, there are no odd multiples of 3. This means that other than 2 and 3, all primes are +/-1 from a multiple of six (try proving that to yourself based on what I've said already). foreach my $each_num ( 2, 3, map { (6*$_-1, 6*$_+1) } 1 .. 1+$prime_candidate/6)
- You are still going much higher than you have to for large numbers. The lowest prime factor of a non-prime will always be less than or equal to the number's square root, so divisor checks shouldn't go beyond that. foreach my $each_num ( 2, 3, map { (6*$_-1, 6*$_+1) } 1 .. 1+sqrt($prime_candidate)/6)
- Read about the Sieve of Eratosthenes if you want to get deeper into algorithm improvements beyond the 2 and 3 divisors.
- when your prime candidate gets too big, you won't be able to use default math; use bigint to go beyond that limitation
(Before posting, I see ++ choroba beat me to most of those algorithm points. I said some things differently, so I am still posting this.)
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|