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];
};
}
And an example of some code using this:
my $iter = prime_iterator();
my $count = 0;
$count++ while $iter->() < 1000000;
print $count;
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.