On my 1GHz machine that code takes 22 seconds to find the first 100,000 primes. Even if you're looking for primes in terms of the "the first x primes", as opposed to terms of "all primes less than y", you can still use a sieve of Eratosthenes - which is siginificantly faster - though you probably need to settle for a little wastefulness. The following code, which is wasteful to the extent that it actually finds the first 105807 primes, does so in less than 2 seconds on the same 1GHz machine. (The wastefulness could be reduced by perhaps lowering $allowance a little closer to 0.5.) If $to_find is set to 1,000,000 it takes about 28 seconds to do the calculation ... and a helluvalot longer to print them out :-)
use warnings;
use strict;

my $t0 = time;

my $to_find = 100000;
my $allowance = 0.6;
my $max = int($to_find * log($to_find) * $allowance);
my $count = 1;

my $imax = sqrt($max * 2 + 1) + 1;
$imax -= 1;
$imax /= 2;

my @bits = (1) x $max;

$bits[0] = 0;

for(my $i = 0; $i < $imax; $i++) {
   if($bits[$i]) {
     my $k = $i * 2 + 1;
     for(my $j = $k + $i; $j < $max; $j += $k) {
        $bits[$j] = 0;
        }
     }
   }

my $t1 = time;

for(my $i = 0; $i < $max; $i++) {
   if($bits[$i]) {
     $count++;
     print $i * 2 + 1, " ";
     if($count == $to_find){last}
     }
   }

print "\nFound at least $count primes in ", $t1 - $t0, " seconds\n";

[download]
I haven't pushed the primes into their own array. In the end @bits encodes the primes, and the creation of a separate array of primes amounts to needless replication. (Of course you can still create the array of primes on the fly if you so desire - it's not massively expensive in terms of time.)

You could also use Bit::Vector's implementation (in C) of the Eratosthenes sieve in much the same way. It's faster and consumes less memory despite the fact that it needlessly encodes even numbers. (@bits in the above code encodes only only odd numbers.)

I don't claim that the above script is thoroughly debugged - nor do I claim that it can't be improved upon .... nor do I claim that it is simpler than the script posted by Grandfather. It's just a lot faster ... and that's about all it has going for it :-)

Cheers,
Rob

In reply to Re: Quick search for modest numbers of prime numbers by syphilis
in thread Quick search for modest numbers of prime numbers by GrandFather

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.