view release on metacpan or  search on metacpan

lib/Math/Prime/FastSieve.pm  view on Meta::CPAN

without the hard work of the folks involved in the Inline and Inline::C
project.  There are many individuals who have contributed and continue to
contribute to the Inline project.  I won't name them all here, but they do
deserve thanks and credit.

Dana Jacobsen provided several optimizations that improved even further on
the speed and memory performance of this module.  Dana's contributions include
reducing the memory footprint of the bit sieve in half, and trimming cycles by
cutting in half the number of iterations of an inner loop in the sieve
generator.  This module started fast and got even faster (and more memory
efficient) with Dana's contributions.

=head1 SEE ALSO

L<Math::Prime::Util> is a much larger Primes library, by Dana Jacobsen.  In
some cases Math::Prime::FastSieve's object-oriented interface may be a better
fit, but generally speaking, Dana's module is a little faster, and supercedes
this module in its functionality and capabilities.

=head1 LICENSE AND COPYRIGHT

Copyright 2011-2014 David Oswald.

This program is free software; you can redistribute it and/or modify it
under the terms of either: the GNU General Public License as published
by the Free Software Foundation; or the Artistic License.

See http://dev.perl.org/licenses/ for more information.


=cut


__DATA__

__CPP__


#include <vector>


using std::vector;


typedef vector<bool> sieve_type;
typedef vector<bool>::size_type sieve_size_t;


/* Class Sieve below.  Perl sees it as a class named
 * "Math::Prime::FastSieve::Sieve".  The constructor is mapped to
 * "new()" within Perl, and the destructor to "DESTROY()".  All other
 * methods are mapped with the same name as declared in the class.
 *
 * Therefore, Perl sees this class approximately like this:
 *
 * package Math::Prime::FastSieve;
 *
 * sub new {
 *     my $class = shift;
 *     my $n     = shift;
 *     my $self = bless {}, $class;
 *     $self->{max_n} = n;
 *     $self->{num_primes} = 0;
 *     # Build the sieve here...
 *     # I won't bother translating it to Perl.
 *     $self->{sieve} = $primes;  // A reference to a bit vector.
 *     return $self;
 *  }
 *
 */


class Sieve
{
  public:
    Sieve ( long n ); // Constructor. Perl sees "new()".
    bool           isprime      ( long n );    // Test if n is prime.
    SV*            primes       ( long n );    // All primes in an aref.
    unsigned long  nearest_le   ( long n );    // Nearest prime <= n.
    unsigned long  nearest_ge   ( long n );    // Nearest prime >= n.
    unsigned long  nth_prime    ( long n );    // The nth prime.
    unsigned long  count_sieve  (        );    // Sieve's prime count.
    unsigned long  count_le     ( long n );    // Number of primes <= n.
    SV*            ranged_primes( long lower, long upper );

  private:
    sieve_size_t   max_n;
    unsigned long  num_primes;
    sieve_type     sieve;
};


// Set up a primes sieve of 0 .. n inclusive.
// This sieve has been optimized to only represent odds, cutting memory
// footprint in half.
Sieve::Sieve( long n ) :max_n(n), num_primes(0), sieve(n/2+1,0)
{
   if( n < 0 ) // Trap negative n's before we start wielding unsigned longs.
        max_n = 0UL;
    else {
        for( sieve_size_t i = 3; i * i <= n; i+=2 )
            if( ! sieve[i/2] )
                for( sieve_size_t k = i*i; k <= n; k += 2*i)
                    sieve[k/2] = 1;
    }
}


// Yes or no: Is the number a prime?  Must be within the range of
// 0 through max_n (the upper limit set by the constructor).
bool Sieve::isprime( long n )
{
    if( n < 2 || n > max_n )  return false; // Bounds checking.
    if( n == 2 )              return true;  // 2 is prime.
    if( ! ( n % 2 ) )         return false; // No other evens are prime.
    if( ! sieve[n/2] )        return true;  // 0 bit signifies prime.
    return false;                           // default: not prime.
}


// Return a reference to an array containing the list of all primes