note
tobyink
<blockquote><p><i>One speedy way is to use the Sieve of Eratosthenes.</i></p></blockquote>
<p>Speedy? Benchmarking mine against yours...</p>
<code>
NUMBER : TOBYINK JOHNGG
NUMBER : RESULT TIME RESULT TIME
75 : NO 0.000065 NO 0.000215
169 : NO 0.000057 NO 0.000649
229 : YES 0.000070 YES 0.000888
367 : YES 0.000073 YES 0.001437
369 : NO 0.000052 NO 0.000805
8794 : NO 0.000051 NO 0.008682
9227 : YES 0.000113 YES 0.031170
10807 : NO 0.000131 NO 0.047135
11939 : YES 0.000121 YES 0.045032
14803 : NO 0.000122 NO 0.054764
19937 : YES 0.000143 YES 0.070692
19938 : NO 0.000040 NO 0.020510
39783 : NO 0.000057 NO 0.065555
47083 : NO 0.000230 NO 0.170125
199933 : YES 0.000346 YES 0.778786
</code>
<p>For some of those higher numbers, mine is about 2000 times faster than yours. The sieve is efficient if you need to generate a list of all prime numbers below x, but very slow as a mechanism for determining whether a given number is prime.</p>
<p>Benchmark script:</p>
<readmore>
<code>
use 5.010;
use strict;
use Carp qw/croak/;
use Time::HiRes qw/time/;
sub isPrime1 (_)
{
my $num = shift;
return if $num == 1; # 1 is not prime
croak "usage: isPrime(NATURAL NUMBER)"
unless $num =~ /^[1-9][0-9]*$/;
for my $div (2 .. sqrt $num)
{
return if $num % $div == 0;
}
return 1;
}
sub isPrime2
{
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);
}
say q[ NUMBER : TOBYINK JOHNGG ];
say q[ NUMBER : RESULT TIME RESULT TIME ];
for my $num (qw(75 169 229 367 369 8794 9227 10807 11939 14803 19937 19938 39783 47083 199933))
{
printf('%8d : ', $num);
timeit($num, $_) for \&isPrime1, \&isPrime2;
print "\n";
}
sub timeit
{
my ($n, $f) = @_;
my $start = time();
print($f->($n) ? "YES " : "NO ");
my $end = time();
printf '%.06f ', ($end - $start);
}
</code>
</readmore>
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-757127">
<small><small>
<tt>perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'
</tt></small></small>
</div></div>
969110
969135