comment on

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
[download]

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

perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'

In reply to Re^2: is it prime? by tobyink
in thread is it prime? by Anonymous Monk

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


The stupid question is the question not asked
	PerlMonks