1Math::Prime::XS(3)    User Contributed Perl Documentation   Math::Prime::XS(3)
2
3
4

NAME

6       Math::Prime::XS - Detect and calculate prime numbers with deterministic
7       tests
8

SYNOPSIS

10        use Math::Prime::XS ':all';
11        # or
12        use Math::Prime::XS qw(is_prime primes mod_primes sieve_primes sum_primes trial_primes);
13
14        print "prime" if is_prime(59);
15
16        @all_primes   = primes(100);
17        @range_primes = primes(30, 70);
18
19        @all_primes   = mod_primes(100);
20        @range_primes = mod_primes(30, 70);
21
22        @all_primes   = sieve_primes(100);
23        @range_primes = sieve_primes(30, 70);
24
25        @all_primes   = sum_primes(100);
26        @range_primes = sum_primes(30, 70);
27
28        @all_primes   = trial_primes(100);
29        @range_primes = trial_primes(30, 70);
30

DESCRIPTION

32       "Math::Prime::XS" detects and calculates prime numbers by either
33       applying Modulo operator division, the Sieve of Eratosthenes, a
34       Summation calculation or Trial division.
35

FUNCTIONS

37   is_prime
38        is_prime($number);
39
40       Returns true if the number is prime, false if not.
41
42       The XS function invoked within is_prime() is subject to change
43       (currently it's an all-XS trial division skipping multiples of 2,3,5).
44
45   primes
46        @all_primes   = primes($number);
47        @range_primes = primes($base, $number);
48
49       Returns all primes for the given number or primes between the base and
50       number.
51
52       The resolved function called is subject to change (currently
53       sieve_primes()).
54
55   count_primes
56        $count = count_primes($number);
57        $count = count_primes($base, $number);
58
59       Return a count of primes from 0 to $number, or from $base to $number,
60       inclusive.  The arguments are the same as primes() but the return is
61       just a count of the primes.
62

SPECIFIC ALGORITHMS

64   mod_primes
65        @all_primes   = mod_primes($number);
66        @range_primes = mod_primes($base, $number);
67
68       Applies the Modulo operator division algorithm:
69
70       Divide the number by 2 and all odd numbers <= sqrt(n); if any divides
71       exactly then the number is not prime.
72
73       Returns all primes between 2 and $number, or between $base and $number
74       (inclusive).
75
76       (This function differs from "trial_primes" in that the latter takes
77       some trouble to divide only by primes below sqrt(n), whereas
78       "mod_primes" divides by all integers not easily identifiable as
79       composite.)
80
81   sieve_primes
82        @all_primes   = sieve_primes($number);
83        @range_primes = sieve_primes($base, $number);
84
85       Applies the Sieve of Eratosthenes algorithm:
86
87       One of the most efficient ways to find all the small primes (say, all
88       those less than 10,000,000) is by using the Sieve of Eratosthenes (ca
89       240 BC). Make a list of all numbers less than or equal to n (and
90       greater than one) and strike out the multiples of all primes less than
91       or equal to the square root of n: the numbers that are left are primes.
92
93       Returns all primes for the given number or primes between the base and
94       number.
95
96       <http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes>
97
98   sum_primes
99        @all_primes   = sum_primes($number);
100        @range_primes = sum_primes($base, $number);
101
102       Applies the Summation calculation algorithm:
103
104       The summation calculation algorithm resembles the modulo operator
105       division algorithm, but also shares some common properties with the
106       Sieve of Eratosthenes. For each saved prime smaller than or equal to
107       the square root of the number, recall the corresponding sum (if none,
108       start with zero); add the prime to the sum being calculated while the
109       summation is smaller than the number. If none of the sums equals the
110       number, then the number is prime.
111
112       Returns all primes for the given number or primes between the base and
113       number.
114
115       <http://www.geraldbuehler.de/primzahlen/>
116
117   trial_primes
118        @all_primes   = trial_primes($number);
119        @range_primes = trial_primes($base, $number);
120
121       Applies the Trial division algorithm:
122
123       To see if an individual small number is prime, trial division works
124       well: just divide by all the primes less than or equal to its square
125       root. For example, to assert 211 is prime, divide by 2, 3, 5, 7, 11 and
126       13. Since none of these primes divides the number evenly, it is prime.
127
128       Returns all primes for the given number or primes between the base and
129       number.
130
131       <http://primes.utm.edu/glossary/page.php?sort=TrialDivision>
132

BENCHMARK

134       Following output resulted from a benchmark measuring the time to
135       calculate primes up to 1,000,000 with 100 iterations for each function.
136       The tests were conducted by the "cmpthese" function of the Benchmark
137       module.
138
139                       Rate   mod_primes trial_primes   sum_primes sieve_primes
140        mod_primes   1.32/s           --         -58%         -79%         -97%
141        trial_primes 3.13/s         137%           --         -49%         -93%
142        sum_primes   6.17/s         366%          97%           --         -86%
143        sieve_primes 43.3/s        3173%        1284%         602%           --
144
145       The "Rate" column is the speed in how many times per second, so
146       sieve_primes() is the fastest for this particular test.
147

EXPORT

149   Functions
150       "is_prime(), primes(), mod_primes(), sieve_primes(), sum_primes(),
151       trial_primes()" are exportable.
152
153   Tags
154       ":all - *()"
155

BUGS & CAVEATS

157       Note that the order of execution speed for functions may differ from
158       the benchmarked results when numbers get larger or smaller.
159

SEE ALSO

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

AUTHOR

165       Steven Schubiger <schubiger@cpan.org>
166

LICENSE

168       This program is free software; you may redistribute it and/or modify it
169       under the same terms as Perl itself.
170
171       See <http://dev.perl.org/licenses/>
172
173
174
175perl v5.36.0                      2023-01-20                Math::Prime::XS(3)
Impressum