That was also my first reaction, but merlyn's algorithm is lightening fast. As is often the case, one trades speed for memory. On modern computers the amount of memory needed to find primes between 1 and 1 million is rarely an issue. The OP is satisfied with the primes < 1 million. If you are looking for very, very large primes (10's of digits) I'm sure other slower algorithms might be better.

Best, beth

No, merlyn was fast because of clever bit-twiddling. Not a good algorithm.

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]

And an example of some code using this:

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

On my laptop my code runs in 0.585s while merlyn's code runs in 1.188s.

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.