use strict; use warnings; use Benchmark qw{ cmpthese }; use Test::More tests => 1; is_deeply( [ primes( 10000 ) ], [ primes_jg( 10000 ) ], 'same' ); cmpthese( -10, { ch => 'primes( 10000 )', jg => 'primes_jg( 10000 )', } ); sub primes_jg { my $limit = shift; my $sqrtLimit = sqrt $limit; my $sieve = q{}; vec( $sieve, 0, 1 ) = 1; vec( $sieve, 1, 1 ) = 1; vec( $sieve, $limit, 1 ) = 0; my @primes; my $reached = 1; while( $reached < $sqrtLimit ) { my $prime = $reached + 1; ++ $prime while vec( $sieve, $prime, 1 ); push @primes, $prime; my $fill = 2 * $prime; while( $fill <= $limit ) { vec( $sieve, $fill, 1 ) = 1; $fill += $prime; } $reached = $prime; } foreach my $value ( $reached + 1 .. $limit ) { push @primes, $value unless vec( $sieve, $value, 1 ); } return @primes; } sub primes { my $n = shift; return if $n < 2; my @primes = (2); for my $i (3 .. $n) { my $sqrt = sqrt $i; my $notprime; for my $p (@primes) { last if $p > $sqrt; $notprime = 1, last if 0 == $i % $p; } push @primes, $i unless $notprime; } return @primes }