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";

##</code><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;