# 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);
}
[download]