On my 1GHz machine that code takes 22 seconds to find the first 100,000 primes. Even if you're looking for primes in terms of the "the first x primes", as opposed to terms of "all primes less than y", you can still use a sieve of Eratosthenes - which is siginificantly faster - though you probably need to settle for a little wastefulness. The following code, which is wasteful to the extent that it actually finds the first 105807 primes, does so in less than 2 seconds on the same 1GHz machine. (The wastefulness could be reduced by perhaps lowering $allowance a little closer to 0.5.) If $to_find is set to 1,000,000 it takes about 28 seconds to do the calculation ... and a helluvalot longer to print them out :-)

use warnings;
use strict;

my $t0 = time;

my $to_find = 100000;
my $allowance = 0.6;
my $max = int($to_find * log($to_find) * $allowance);
my $count = 1;

my $imax = sqrt($max * 2 + 1) + 1;
$imax -= 1;
$imax /= 2;

my @bits = (1) x $max;

$bits[0] = 0;

for(my $i = 0; $i < $imax; $i++) {
   if($bits[$i]) {
     my $k = $i * 2 + 1;
     for(my $j = $k + $i; $j < $max; $j += $k) {
        $bits[$j] = 0;
        }
     }
   }

my $t1 = time;

for(my $i = 0; $i < $max; $i++) {
   if($bits[$i]) {
     $count++;
     print $i * 2 + 1, " ";
     if($count == $to_find){last}
     }
   }

print "\nFound at least $count primes in ", $t1 - $t0, " seconds\n";
[download]

I haven't pushed the primes into their own array. In the end @bits encodes the primes, and the creation of a separate array of primes amounts to needless replication. (Of course you can still create the array of primes on the fly if you so desire - it's not massively expensive in terms of time.)

You could also use Bit::Vector's implementation (in C) of the Eratosthenes sieve in much the same way. It's faster and consumes less memory despite the fact that it needlessly encodes even numbers. (@bits in the above code encodes only only odd numbers.)

I don't claim that the above script is thoroughly debugged - nor do I claim that it can't be improved upon .... nor do I claim that it is simpler than the script posted by Grandfather. It's just a lot faster ... and that's about all it has going for it :-)

Cheers,
Rob