in reply to Re: is it prime?
in thread is it prime?
One speedy way is to use the Sieve of Eratosthenes.
Speedy? Benchmarking mine against yours...
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
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.
Benchmark script:
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 1 +9938 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); }
perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^3: is it prime?
by johngg (Canon) on May 09, 2012 at 09:33 UTC | |
by danaj (Friar) on Jun 09, 2014 at 08:57 UTC |
In Section
Seekers of Perl Wisdom