One speedy way is to use the Sieve of Eratosthenes.
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 );
}
The output.
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
I quickly adapted this from a much older program I had lying around that lists all the primes up to a limit.
# 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);
}
I hope this is of interest.
Update: Not so speedy, apparently! If only I had a computer science background and understood all the O(log n) gubbins :-D
Also updated the broken link.
