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 had a play years ago with primes and thought I had a pretty good algorithm until someone told me about Eratosthenes. Using his method was much faster. I have tried one variation since which was to use a vector to hold the primes rather than an array/list. The script will print primes as it goes until it reaches the threshhold of sqrt(limit) at which point it knows it has filled the vector up to the limit we have given. After that it prints the rest as fast as the frame buffer can handle.

#!/usr/local/bin/perl -w
#
$limit = shift or die "No limit supplied\n";
die "Limit is not integer\n" unless $limit =~ /^\d+$/;
$sqrtLimit = sqrt $limit;
$sieve = "";
vec($sieve, 0, 1) = 1;
vec($sieve, 1, 1) = 1;
vec($sieve, $limit, 1) = 0;
$reached = 1;
while($reached < $sqrtLimit)
{
    $prime = $reached + 1;
    ++ $prime while vec($sieve, $prime, 1);
    print "$prime is a prime\n";
    $fill = 2 * $prime;
    while($fill <= $limit)
    {
        vec($sieve, $fill, 1) = 1;
    $fill += $prime;
    }
    $reached = $prime;
}
foreach $value ($reached + 1 .. $limit)
{
    print "$value is a prime\n" unless vec($sieve, $value, 1);
}
[download]

On an ancient SPARCstation 20 with 150MHz processor it will calculate and print primes up to 100,000 in under 10 seconds.

Cheers

JohnGG