NAME
   Math::Prime::XS - Calculate/detect prime numbers with deterministic
   tests

SYNOPSIS
    use Math::Prime::XS ':all';
    # or
    use Math::Prime::XS qw(primes is_prime mod_primes sieve_primes sum_primes trial_primes);

    @all_primes   = primes(9);
    @range_primes = primes(4, 9);

    if (is_prime(11)) { # do stuff }

    @all_primes   = mod_primes(9);
    @range_primes = mod_primes(4, 9);

    @all_primes   = sieve_primes(9);
    @range_primes = sieve_primes(4, 9);

    @all_primes   = sum_primes(9);
    @range_primes = sum_primes(4, 9);

    @all_primes   = trial_primes(9);
    @range_primes = trial_primes(4, 9);

DESCRIPTION
   "Math::Prime::XS" calculates/detects prime numbers by either applying
   Modulo operator division, the Sieve of Eratosthenes, Trial division or a
   Summing calculation.

FUNCTIONS
 primes
   Takes an integer and calculates the primes from 0 <= integer. Optionally
   an integer may be provided as first argument which will function as
   limit. Calculation then will take place within the range of the limit
   and the integer. Calls "sum_primes()" beneath the surface.

 is_prime
   Takes an integer as input and returns 1 if integer is prime, 0 if it
   isn't. The underlying algorithm has been taken from "sum_primes()".

 mod_primes
   Applies the Modulo operator division and provides same functionality and
   interface as "primes()". Divides the number by all n less or equal then
   the number; if the number gets exactly two times divided by rest null,
   then the number is prime, otherwise not.

 sieve_primes
   Applies the Sieve of Erathosthenes and provides same functionality and
   interface as "primes()". The most efficient way to find all of the small
   primes (say all those less than 10,000,000) is by using the Sieve of
   Eratosthenes (ca 240 BC): Make a list of all the integers less than or
   equal to n (and greater than one). Strike out the multiples of all
   primes less than or equal to the square root of n, then the numbers that
   are left are the primes.

   <http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes>

 sum_primes
   Applies a Summing calculation that is somehow similar to
   "trial_primes()"; provides same functionality and interface as
   "primes()". Compared to "trial_primes()", Trial division is being
   omitted and replaced by an addition of primes less than the number's
   square root. If one of the "multiples" equals the number, then the
   number is not prime, otherwise, it is. This algorithm is a somewhat
   hybrid between the Sieve of Eratosthenes and Trial division.

   <http://www.geraldbuehler.de/primzahlen>

 trial_primes
   Applies Trial division and provides the same functionality and interface
   as "primes()". To see if an individual small integer is prime, Trial
   division works well: just divide by all the primes less than (or equal
   to) its square root. For example, to show 211 is prime, just divide by
   2, 3, 5, 7, 11, and 13. Since none of these divides the number evenly,
   it is a prime.

   <http://primes.utm.edu/glossary/page.php?sort=TrialDivision>

BENCHMARK
   If one appends "_primes" to the names on the left, one gets the full
   subnames. Following benchmark output refers to output generated by the
   "cmpthese()" function of the Benchmark module.

   Calculation results:

   primes <= 4000, one iteration:

             Rate sieve   mod trial   sum
    sieve 0.333/s    --  -97%  -98%  -99%
    mod    11.9/s 3478%    --  -33%  -57%
    trial  17.9/s 5277%   50%    --  -35%
    sum    27.6/s 8186%  132%   54%    --

   primes <= 8000, one iteration:

                Rate sieve   mod   sum trial
    sieve 7.71e-02/s    --  -98%  -99%  -99%
    mod       3.31/s 4188%    --  -53%  -54%
    sum       7.00/s 8979%  112%    --   -2%
    trial     7.14/s 9164%  116%    2%    --

   Bear in mind, that these results are not too reliable as the author
   could neither increase the number nor the iteration count provided,
   because if he attempted to do so, perl would report "Out of memory!",
   which was most likely caused by the Sieve of Eratosthenes algorithm,
   which is rather memory exhaustive by implementation. The Sieve of
   Eratosthenes is expected to be the slowest, followed by the Modulo
   operator division, then either Summing calculation or Trial division
   (dependant upon the iterations) followed by its counterpart.

EXPORT
 Functions
   "primes(), is_prime(), mod_primes(), sieve_primes(), sum_primes(),
   trial_primes()" are exportable.

 Tags
   ":all - *()"

SEE ALSO
   <http://primes.utm.edu>,
   <http://www.it.fht-esslingen.de/~schmidt/vorlesungen/kryptologie/seminar
   /ws9798/html/prim/prim-1.html>

AUTHOR
   Steven Schubiger <[email protected]>

LICENSE
   This program is free software; you may redistribute it and/or modify it
   under the same terms as Perl itself.

   See <http://www.perl.com/perl/misc/Artistic.html>

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.