Re: [MacPerl] What's wrong?

[Terje Bless <link@tss.no>]

Paul J. Schinder wrote:
>I'm sure there must be prime finding algorithms (factoring is the technical
>term, if I remember right) all over the place.

Yes, there are. It`s called the "Sieve of Erathostenes" and according to
Abigail <abigail@fnx.com> in <URL:news:EBEB4r.Jn7@nonexistent.com>
(Slightly edited!):

--- Begin forwarded material

One of the simplest (and one of the fastest methods) is the
sieve of Eratosthenes. Known for eons. (23 centuries [0])

Here's an implementation:

#!/usr/local/bin/perl -wl
use strict;
 
my ($prime, $max) = (2, shift || 50);          # First prime, max
number.
my @sieve = (0, 0, map {1;} ($prime .. $max)); # Init sieve.
 
while ((my $product = $prime * $prime) <= $max) {
  do {$sieve [$product] = 0;} while (($product += $prime) <= $max);
  do {$prime ++;}             while !$sieve [$prime];
}
 
map {print if $sieve [$_];} (0 .. $max);
__END__


[0]
<URL:http://www.utexas.edu/depts/grg/ustudent/frontiers/fall95/morrison/morrison.html>

--- End forwarded material

An alternative to Abigail`s implementation is to use Bit::Vector and the
accompanying primes.pl example program. Both by Steffen Beyer
<sb@en.muc.de>. It`s still the "Sieve of Erathostenes" but it`s
implemented using Bit::Vector which is written entirely in C and has
been extensively optimized. The catch (there _had_ to be one! ;D) is
that Bit::Vector may not be available on Mac OS.


BTW: We`re moving away from MacPerl and into algorithms and generic
modules here. Further discussion might perhaps better be taken to
<URL:news:comp.lang.perl.misc> and/or <URL:news:comp.lang.perl.modules>
(Charter for MacPerl-L said MacPerl-specific *only* last time I looked
(of course, my memory is a bit fuzzy, so I may be wrong ;D)).

-- 
Party? Party, lord? Yes, lord. Right away, lord.
        - Beopunk Cyberwulf

***** Want to unsubscribe from this list?
***** Send mail with body "unsubscribe" to mac-perl-request@iis.ee.ethz.ch