The sieve of Eratosthenes is a good algorithm. It requires N bits of storage for primes to N.
Here is a pure-perl implementation, using 'vec' for the bit array and done as an OO perl module built around a blessed scalar reference (to the bit array). It isn't heavily tested, I'm afraid, but you use it as follows:
use Sieve; # Rename as appropriate...
my $sieve = Sieve->new;
foreach my $number (qw/13 20 35 3/) {
print "$number is ",
$sieve->is_prime($number) ? "prime" : "composite", "\n";
}
print join(", ", $sieve->primes_to(300)), "\n";
And here is the code:
package Sieve;
use strict;
use warnings;
my $BITS_PER_BYTE = 8;
my $INITIAL_SIZE = $BITS_PER_BYTE ** 2;
sub new {
# A sieve is a bit array, where 'true' => composite
my $sieve = '';
# 0 isn't prime
vec($sieve, 0, 1) = 1;
# 1 isn't prime
vec($sieve, 1, 1) = 1;
my $s = \$sieve;
bless $s, __PACKAGE__;
# Pre-extend the array
vec($sieve, $INITIAL_SIZE, 1) = 0;
# And fill it in
$s->_run;
return $s;
}
sub is_prime {
my $s = shift;
my $n = shift;
$s->_extend($n);
return !vec($$s, $n, 1);
}
sub primes_to {
my $s = shift;
my $n = shift;
$s->_extend($n);
return grep { $s->is_prime($_) } 1..$n;
}
sub _run {
my $s = shift;
my $i;
my $limit = sqrt ($s->_size);
for ($i = 2; $i < $limit; ++$i) {
next unless $s->is_prime($i);
$s->_mark_multiples($i);
}
}
sub _extend {
my $s = shift;
my $to = shift;
return 0 if $to <= $s->_size;
vec($$s, $to, 1) = 0;
return $s->_run;
}
sub _mark_multiples {
my $s = shift;
my $p = shift;
my $i;
my $limit = $s->_size;
for ($i = 2 * $p; $i < $limit; $i += $p) {
vec($$s, $i, 1) = 1;
}
}
sub _size {
my $s = shift;
return (length $$s) * $BITS_PER_BYTE;
}
1;