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 ); }