NAME
   Math::Prime::XS - Detect and calculate prime numbers with deterministic
   tests

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

    print "prime" if is_prime(59);

    @all_primes   = primes(100);
    @range_primes = primes(30, 70);

    @all_primes   = mod_primes(100);
    @range_primes = mod_primes(30, 70);

    @all_primes   = sieve_primes(100);
    @range_primes = sieve_primes(30, 70);

    @all_primes   = sum_primes(100);
    @range_primes = sum_primes(30, 70);

    @all_primes   = trial_primes(100);
    @range_primes = trial_primes(30, 70);

DESCRIPTION
   `Math::Prime::XS' detects and calculates prime numbers by either
   applying Modulo operator division, the Sieve of Eratosthenes, a
   Summation calculation or Trial division.

FUNCTIONS
 is_prime

    is_prime($number);

   Returns true if the number is prime, false if not.

   The XS function invoked within `is_prime()' is subject to change
   (currently `xs_sieve_primes()').

 primes

    @all_primes   = primes($number);
    @range_primes = primes($base, $number);

   Returns all primes for the given number or primes between the base and
   number.

   The resolved function called is subject to change (currently
   `sieve_primes()').

 mod_primes

    @all_primes   = mod_primes($number);
    @range_primes = mod_primes($base, $number);

   Applies the Modulo operator division algorithm:

   Divide the number by all numbers less or equal than itself; if the
   number is divided exactly two times by the modulo operator without rest,
   then the number is prime.

   Returns all primes for the given number or primes between the base and
   number.

 sieve_primes

    @all_primes   = sieve_primes($number);
    @range_primes = sieve_primes($base, $number);

   Applies the Sieve of Eratosthenes algorithm:

   One of the most efficient ways to find all 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 numbers less than or equal to n (and greater
   than one) and strike out the multiples of all primes less than or equal
   to the square root of n: the numbers that are left are primes.

   Returns all primes for the given number or primes between the base and
   number.

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

 sum_primes

    @all_primes   = sum_primes($number);
    @range_primes = sum_primes($base, $number);

   Applies the Summation calculation algorithm:

   The summation calculation algorithm resembles the modulo operator
   division algorithm, but also shares some common properties with the
   Sieve of Eratosthenes. For each saved prime smaller than or equal to the
   square root of the number, recall the corresponding sum (if none, start
   with zero); add the prime to the sum being calculated while the
   summation is smaller than the number. If none of the sums equals the
   number, then the number is prime.

   Returns all primes for the given number or primes between the base and
   number.

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

 trial_primes

    @all_primes   = trial_primes($number);
    @range_primes = trial_primes($base, $number);

   Applies the Trial division algorithm:

   To see if an individual small number is prime, trial division works
   well: just divide by all the primes less than or equal to its square
   root. For example, to assert 211 is prime, divide by 2, 3, 5, 7, 11 and
   13. Since none of these primes divides the number evenly, it is prime.

   Returns all primes for the given number or primes between the base and
   number.

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

BENCHMARK
   Following output resulted from a benchmark measuring the time to
   calculate primes up to 1,000,000 with 100 iterations for each function.
   The tests were conducted by the `cmpthese' function of the Benchmark
   module.

                      Rate   mod_primes   sum_primes trial_primes sieve_primes
   mod_primes   6.39e-03/s           --        -100%        -100%        -100%
   sum_primes       8.10/s      126540%           --         -41%         -89%
   trial_primes     13.6/s      212979%          68%           --         -82%
   sieve_primes     74.6/s     1167064%         822%         448%           --

EXPORT
 Functions

   `is_prime(), primes(), mod_primes(), sieve_primes(), sum_primes(),
   trial_primes()' are exportable.

 Tags

   `:all - *()'

BUGS & CAVEATS
   Note that the order of execution speed for functions may differ from the
   benchmarked results when numbers get larger or smaller.

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://dev.perl.org/licenses/

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.