Hey, that looks pretty cool and I'll see what I can do to implement that, once I've worked out the math (it doesn't look too hard). In the meantime, here's a much faster version, easier to read version, based upon an article by merlyn.

#!/usr/bin/perl
use warnings;
use strict;
use Data::Dumper;

sub NEXT ($) { $_[0]->() }

sub prime_iterator {
    my $num = 0;
    sub {
        do {
            $num++;
        } until is_prime($num);
        return $num;
    }
}

sub is_prime {
    my $guess = shift;
    for (my $divisor = 2; $divisor * $divisor <= $guess; $divisor++) {
        return unless $guess % $divisor;
    }
    return 1;
}

my $prime = prime_iterator;
my @primes;
push @primes => NEXT $prime for (1 .. shift || 10);
print Dumper \@primes;
[download]

Cheers,
Ovid

Update: Here's a better "is_prime" function, based upon a code snippet provided in the link the greenback mentioned. This is twice as fast as the above function.

sub is_prime {
    my $guess = shift;
    # accidentally reversed next two lines. Thanks to petral for catch
+ing that :)
    return 1 if $guess == 2;
    return unless $guess > 2 and $guess % 2;

    my $max = 1 + int $guess ** .5;
    for ( my $divisor = 3; $divisor < $max; $divisor += 2 ) {
        return unless $guess % $divisor;
    }
    return 1;
}
[download]

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

It might help to replace the $num++ by $num += 2 since 2 is the only prime number that is even. This saves you half the tests for primality if you have 2 as a special case.

Best, -gjb-

It would be faster were it not for the absurd function call overhead in Perl. :-(

use strict;
sub build_sieve {
  my $n = 0;
  my @upcoming_factors = ();
  my ($next_small_p, $sub_iter);
  my $gives_next_square = 5;
  
  return sub {
    LOOP: {
      if (not $n++) {
        return 2; # Special case
      }
      if (not defined $upcoming_factors[0]) {
        if ($n == $gives_next_square) {
          if (not defined ($sub_iter)) {
            # Be lazy to avoid an infinite loop...
            $sub_iter = build_sieve();
            $sub_iter->(); # Throw away 2
            $next_small_p = $sub_iter->();
          }
  
          push @{$upcoming_factors[$next_small_p]}, $next_small_p;
          $next_small_p = $sub_iter->();
          my $next_p2 = $next_small_p * $next_small_p;
          $gives_next_square = ($next_p2 + 1)/2;
          shift @upcoming_factors;
          redo LOOP;
        }
        else {
          shift @upcoming_factors;
          return 2*$n-1;
        }
      }
      else {
        foreach my $i (@{$upcoming_factors[0]}) {
          push @{$upcoming_factors[$i]}, $i;
        }
        shift @upcoming_factors;
        redo LOOP;
      }
    }
  }
}

my $sieve = build_sieve();
print $sieve->(), "\n" for 1..(shift || 100);
[download]