The sieve of Eratosthenes is a good algorithm. It requires N bits of storage for primes to N.

Here is a pure-perl implementation, using 'vec' for the bit array and done as an OO perl module built around a blessed scalar reference (to the bit array). It isn't heavily tested, I'm afraid, but you use it as follows: 

use Sieve; # Rename as appropriate...

my $sieve = Sieve->new;
foreach my $number (qw/13 20 35 3/) {
    print "$number is ",
    $sieve->is_prime($number) ? "prime" : "composite", "\n";
}
print join(", ", $sieve->primes_to(300)), "\n";

[download]
And here is the code: 
package Sieve;
use strict;
use warnings;

my $BITS_PER_BYTE = 8;
my $INITIAL_SIZE = $BITS_PER_BYTE ** 2;

sub new {

    # A sieve is a bit array, where 'true' => composite
    my $sieve = '';
    # 0 isn't prime
    vec($sieve, 0, 1) = 1; 
    # 1 isn't prime
    vec($sieve, 1, 1) = 1; 

    my $s = \$sieve;
    bless $s, __PACKAGE__;
    # Pre-extend the array
    vec($sieve, $INITIAL_SIZE, 1) = 0; 

    # And fill it in
    $s->_run;
    return $s;
}

sub is_prime {
    my $s = shift;
    my $n = shift;

    $s->_extend($n);

    return !vec($$s, $n, 1);
}

sub primes_to {
    my $s = shift;
    my $n = shift;
    $s->_extend($n);
    return grep { $s->is_prime($_) } 1..$n;
}

sub _run {
    my $s = shift;

    my $i;
    my $limit = sqrt ($s->_size);
    for ($i = 2; $i < $limit; ++$i) {
        next unless $s->is_prime($i);
        $s->_mark_multiples($i);
    }
}

sub _extend {
    my $s = shift;
    my $to = shift;

    return 0 if $to <= $s->_size;
    vec($$s, $to, 1) = 0;

    return $s->_run;
}

sub _mark_multiples {
    my $s = shift;
    my $p = shift;

    my $i;
    my $limit = $s->_size;
    for ($i = 2 * $p; $i < $limit; $i += $p) {
        vec($$s, $i, 1) = 1;
    }
}

sub _size {
    my $s = shift;
    return (length $$s) * $BITS_PER_BYTE;
}

1;

[download]

In reply to Re: Math help: Finding Prime Numbers by jbert
in thread Math help: Finding Prime Numbers by Ovid

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.