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";