There are many simple prime number algorightms around, unfortunately the simple ones aren't efficient. The Sieve of Erastothenes is a classic example. I do not know of any perl modules that explicitly implement prime number type functionality. Below is a simple and extermely inefficient is_prime function.

sub is_prime{
  my $n=shift;
  return 0 if($n != int($n));
  my $m=sqrt($n);
  for(my $c=2;$c<=$m;$c++){
    return 0 if($n/$c == int($n/$c));
  }
  return 1;
}
[download]

Any way you slice it, I don't think Perl is the best language for a high performance prime number analyzer. Your best bet would be to find a language designed explicitly for doing large number math if you seriously want to go after a "largest prime number" record.

Thanks lhoward. I looked at the web page that you recommended and it helped me some with my thought on how I am going to approach the math in this project. As for your suggestion to use another, more mathematically inclined language, it's not an issue for me because this project is to learn Perl (and stick it to the man).

redmist
redmist.dyndns.org
redmist@users.sourceforge.net

Here's my attempt at a Sieve of Eratothenes... I don't use grep that much, so I won't claim that this works...

@numbers = (2 .. 1_000_000);
@primes = ( );

while (my $prime = shift @numbers) {
  push @primes,$prime;
  @numbers = grep { ($_ % $prime) != 0 } @numbers;
} 

print $primes;
[download]

For an implementation of the Rabin-Miller test, see this node

I though women were from Venus? You know the really hot poisonous planet. Not the mild (in terms of other planets out there) almost livable planet called Mars :) . Why else do you think they put up with 'our' antics -- they need the real estate!

Cheers,
Gryn

p.s. Ow! In advanced to all the --'s I'm about to get. :)

Oh yeah, I keep forgetting that.

Just Another Perl Hacker

sieve of erothenes

Alan