RE: [MacPerl] Prime Numbers

["Creede Lambard (Volt Computer)" <a-creela@microsoft.com>]

Here's my cut at a faster algorithm. I was actually able to stand watching
it run up to 500000, as opposed to the pattern-matching one. :)

# perl 
#
# primefind 0.1
# program to figure primes as long as you care to let it run
# (c) 1999 Creede Lambard. Distributed under the same terms as Perl.
#

open(PRIMES,">Macintosh HD:Desktop Folder:Primes") or die "Can't write: $!";
@primes = (2);
print "2\n";
print PRIMES "2\n";
while (1)
{
     my @temp = ();
     my $highest = $primes[scalar(@primes)-1];    # of items in @primes
     for ($highest..($highest * $highest))
     {   
         my $candidate = $_;
         my $flag = 1;
         foreach $test (@primes)
         {
             if (($candidate/$test) == int($candidate/$test))              
             {
                  $flag = 0;
                  last
             }
         }
         if ($flag)
         {
             print $candidate,"\n";
             print PRIMES $candidate,"\n";
             push @temp,$candidate;
         }
    }
    push @primes,@temp;
    @primes = sort {$a <=> $b} @primes;
}

END {close PRIMES;}

#
#
#

This has the advantage that it will stop and punt out of the loop as soon as
it finds any factor. There are probably ways to optimize it further, but
like I said, this is a first cut.

I suppose you could also create an Eratosthenes' Sieve based on a
million-bit vector, but that's getting *silly*.

-- Creede

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