use strict;
use warnings;

use 5.010;

say
   qq{$_ is },
   isPrime( $_ ) ? q{} : q{not },
   q{prime}
   for 75, 169, 229, 367, 369, 8794, 9227;

sub isPrime
{
    my $toTest    = shift;
    my $sqrtLimit = sqrt $toTest;
    
    my $sieve = q{};
    vec( $sieve, 0      , 1 ) = 1;
    vec( $sieve, 1      , 1 ) = 1;
    vec( $sieve, $toTest, 1 ) = 0;

    my $marker = 1;
    while ( $marker < $sqrtLimit )
    {
        my $possPrime = $marker + 1;
        $possPrime ++ while vec( $sieve, $possPrime, 1 );

        my $fill = 2 * $possPrime;
        while ( $fill <= $toTest )
        {
            vec( $sieve, $fill, 1 ) = 1;
            $fill += $possPrime;
        }
        last if vec( $sieve, $toTest, 1 );

        $marker = $possPrime;
    }

    return not vec( $sieve, $toTest, 1 );
}

##</code><code>##

75 is not prime
169 is not prime
229 is prime
367 is prime
369 is not prime
8794 is not prime
9227 is prime

##</code><code>##

# Script to find prime numbers up to a given limit using
# the algorithm called "The Sieve of Eratosthenes." The
# "sieve" is filled by marking multiples of each prime found
# as "not a prime" so the first prime we find is 2 and so
# all even numbers are marked. The next number along the
# "sieve" that is not marked will be 3 so all multiples of
# 3 are then marked, und so weiter.
#
use strict;
use warnings;

# Read number to find primes up to from command-line and
# make sure it is a positive integer. Algorithm has found
# and marked all non-primes up to $limit once the value
# being examined exceeds the square root of $limit so
# set up that value to avoid recalulation each time.
#
my $limit = shift or die qq{No limit supplied\n};
die qq{Limit is not a positive integer\n} unless
   $limit =~ /^\+?\d+$/;
my $sqrtLimit = sqrt $limit;

# Initialise the "sieve," for which we use a vector. The
# numbers 0 and 1 are not prime so set their positions
# in the vector to true. Assume that our $limit is a
# prime for now by setting to false. We now have a vector
# of the correct length.
#
my $sieve = q{};
vec( $sieve, 0, 1 ) = 1;
vec( $sieve, 1, 1 ) = 1;
vec( $sieve, $limit, 1 ) = 0;

# In initialising the "sieve" we have reached number 1
# so iterate in a while loop until we pass $sqrtLimit.
#
my $reached = 1;
while ( $reached < $sqrtLimit )
{
    # Examine the next number after $reached and keep
    # moving along until we find a number that hasn't
    # been marked as "not a prime."
    #
    my $prime = $reached + 1;
    ++ $prime while vec( $sieve, $prime, 1 );

    # This is a prime so print it out, mark multiples
    # of the prime we have found as "not a prime" up
    # to our $limit. Update where we have reached.
    #
    print qq{$prime is a prime\n};
    my $fill = 2 * $prime;
    while ( $fill <= $limit )
    {
        vec( $sieve, $fill, 1 ) = 1;
	$fill += $prime;
    }
    $reached = $prime;
}

# We have passed $sqrtLimit so all primes up to $limit have
# been found. It just remains to print them out.
#
foreach my $value ( $reached + 1 .. $limit )
{
    print qq{$value is a prime\n} unless vec($sieve, $value, 1);
}