The simple optimization of special casing 2 will result in doubling the speed of his algorithm.

Just to demonstrate this to you, here is the prime generating code that I use for Project Euler problems:

my @primes = (2, 3, 5, 7, 11);          # None have been tested

sub more_primes {
  # This adds to the list of primes until it reaches $max
  #      or the square of the largest current prime (assumed odd)
  my $base = shift || $primes[-1]+1;
  my $max = shift || $base + 10_000;
  my $square = $primes[-1] * $primes[-1];
  $max = $square if $square < $max;     # Determine what to find prime
+s to
  $base++ unless $base % 2;             # Make the base odd
  $max-- if $max %2;                    # Make the max odd
  $max = ($max - $base)/2;              # Make $max into a count of od
+ds
  return if $max < 0;                   # Sanity check
  my $more = "";                        # Initialize vector of 0's for
+ the
                                        # odd numbers in our range
  shift @primes;                        # Remove 2
  foreach my $p (@primes) {
    my $start;
    if ($base < $p * $p) {
      $start = ($p * $p - $base)/2;     # Start at the square
      if ($max < $start) {              # Rest of primes don't matter!
          last;
      }
    }
    else {                              # Start at first odd it divide
+s
      $start = $base % $p;              # Find remainder
      $start = $p - $start if $start;   # Distance to first thing it d
+ivides
      $start += $p if $start %2;        # Distance to first odd it div
+ides
      $start = $start/2;                # Reindex for counting over od
+d!
    }
    for (my $i = $start; $i <= $max; $i += $p) {
      vec($more, $i, 1) = 1;
    }
  }
  unshift @primes, 2;                   # Replace 2
  # Read off list of primes
  push @primes, map {$_ + $_ + $base} grep {vec($more, $_, 1) == 0} 0.
+.$max;
}

sub ith_prime {
  my $i = shift;
  while ($i > $#primes) {
    more_primes();
  }
  return $primes[$i];
}

sub prime_iterator {
  my $i = -1;

  return sub {
    $i++;
    if ($i > $#primes) {
      more_primes();
    }
    return $primes[$i];
  };
}
[download]

my $iter = prime_iterator();
my $count = 0;
$count++ while $iter->() < 1000000;
print $count;
[download]

Note that I could make this code a third faster by special casing 3. But I haven't done this because the prime generating code has never yet been a bottleneck for me. I can generate all of the primes up to 50,000,000 in 33.932s.

However if you need to generate primes *very* quickly, look up http://cr.yp.to/primegen.html. It bit twiddles better than merlyn, uses a better algorithm and is written in C for massively greater efficiency. Seriously, piping input from this program is much, much faster than anything you can do in Perl.