Re: [MacPerl] Prime Numbers

[Matthew Langford <langfml [at] eng [dot] auburn [dot] edu>]

On Mon, 16 Aug 1999, Bill Jones wrote:

>while (++$_) {
> print "",
>  (((1x $_) !~ /^(11+)\1+$/) ? "Yes $_ is prime; found " .++$idx." numbers"
>: next ),
> "\n";
>}

This program puzzled me; the following is how I understand it (I hope
I'm not the last to figure this out...):

What is an obvious (brute force) way of testing for primes?  Isn't it to
try dividing by all the numbers less than it?

We have a number Y, and we want to know if X divides it evenly.  So we lay
out Y number of sticks on the ground, and we gather them into bundles with
X sticks in each bundle.  If there are no sticks left over, it divided
evenly.

That is what this algorithm does, only it is using the pattern matching
engine to do all the work.

1 x $_ lays out a bunch of sticks (1s), $_ number of them.

/^(11+)\1+$/  is looking for evenly divisible groups in the 1s.


Elegantly crude.  Downright clever.

As far as speeding things up, you would probably have to use a completely
different approach.  The obvious improvements to the brute force approach
are to test only the other primes that we've found so far, and to stop
testing once we've reached the square root of the number (at least one
factor must be in this region, if any factors exist). I don't think the
perl pattern matching engine is clever enough to do these--this may only
be useful for this one pattern, after all.  I can't think of a revised
pattern matching expression that would embody these extra "next"s.

For a wee speedup, you could start $_ at 3, manually print 2 and 3, and
increment by 2 (skipping all even numbers).

There are faster ways than even the cleaned-up version of ol' BruteForce,
though. If you are looking for one, you can probably look one up in
various algorithms cookbooks (probably not in Perl).  Or download the
source to a public key encryption system like RSA (SSL and ssh both
usually include RSA); I believe RSA depends on the key being a prime
number.

Thank you for allowing me to dump some of this usefulness-impaired
knowledge on you!  :)


--
MattLangford 


===== Want to unsubscribe from this list?
===== Send mail with body "unsubscribe" to macperl-request@macperl.org