I had a play years ago with primes and thought I had a pretty good algorithm until someone told me about Eratosthenes. Using his method was much faster. I have tried one variation since which was to use a vector to hold the primes rather than an array/list. The script will print primes as it goes until it reaches the threshhold of sqrt(limit) at which point it knows it has filled the vector up to the limit we have given. After that it prints the rest as fast as the frame buffer can handle. 
#!/usr/local/bin/perl -w
#
$limit = shift or die "No limit supplied\n";
die "Limit is not integer\n" unless $limit =~ /^\d+$/;
$sqrtLimit = sqrt $limit;
$sieve = "";
vec($sieve, 0, 1) = 1;
vec($sieve, 1, 1) = 1;
vec($sieve, $limit, 1) = 0;
$reached = 1;
while($reached < $sqrtLimit)
{
    $prime = $reached + 1;
    ++ $prime while vec($sieve, $prime, 1);
    print "$prime is a prime\n";
    $fill = 2 * $prime;
    while($fill <= $limit)
    {
        vec($sieve, $fill, 1) = 1;
    $fill += $prime;
    }
    $reached = $prime;
}
foreach $value ($reached + 1 .. $limit)
{
    print "$value is a prime\n" unless vec($sieve, $value, 1);
}

[download]

On an ancient SPARCstation 20 with 150MHz processor it will calculate and print primes up to 100,000 in under 10 seconds.

Cheers

JohnGG

In reply to Re^2: Quick search for modest numbers of prime numbers by johngg
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.