1Math::Prime::XS(3) User Contributed Perl Documentation Math::Prime::XS(3)
2
6 Math::Prime::XS - Detect and calculate prime numbers with deterministic
7 tests
8
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 print "prime" if is_prime(59);
15 @all_primes = primes(100);
17 @range_primes = primes(30, 70);
18 @all_primes = mod_primes(100);
20 @range_primes = mod_primes(30, 70);
21 @all_primes = sieve_primes(100);
23 @range_primes = sieve_primes(30, 70);
24 @all_primes = sum_primes(100);
26 @range_primes = sum_primes(30, 70);
27 @all_primes = trial_primes(100);
29 @range_primes = trial_primes(30, 70);
30
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
37 is_prime
38 is_prime($number);
39 Returns true if the number is prime, false if not.
41 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 primes
46 @all_primes = primes($number);
47 @range_primes = primes($base, $number);
48 Returns all primes for the given number or primes between the base and
50 number.
51 The resolved function called is subject to change (currently
53 "sieve_primes()").
54 count_primes
56 $count = count_primes($number);
57 $count = count_primes($base, $number);
58 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
64 mod_primes
65 @all_primes = mod_primes($number);
66 @range_primes = mod_primes($base, $number);
67 Applies the Modulo operator division algorithm:
69 Divide the number by 2 and all odd numbers <= sqrt(n); if any divides
71 exactly then the number is not prime.
72 Returns all primes between 2 and $number, or between $base and $number
74 (inclusive).
75 (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 sieve_primes
82 @all_primes = sieve_primes($number);
83 @range_primes = sieve_primes($base, $number);
84 Applies the Sieve of Eratosthenes algorithm:
86 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 Returns all primes for the given number or primes between the base and
94 number.
95 <http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes>
97 sum_primes
99 @all_primes = sum_primes($number);
100 @range_primes = sum_primes($base, $number);
101 Applies the Summation calculation algorithm:
103 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 Returns all primes for the given number or primes between the base and
113 number.
114 <http://www.geraldbuehler.de/primzahlen/>
116 trial_primes
118 @all_primes = trial_primes($number);
119 @range_primes = trial_primes($base, $number);
120 Applies the Trial division algorithm:
122 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 Returns all primes for the given number or primes between the base and
129 number.
130 <http://primes.utm.edu/glossary/page.php?sort=TrialDivision>
132
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 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 The "Rate" column is the speed in how many times per second, so
146 "sieve_primes()" is the fastest for this particular test.
147
149 Functions
150 "is_prime(), primes(), mod_primes(), sieve_primes(), sum_primes(),
151 trial_primes()" are exportable.
152 Tags
154 ":all - *()"
155
157 Note that the order of execution speed for functions may differ from
158 the benchmarked results when numbers get larger or smaller.
159
161 <http://primes.utm.edu>,
162 <http://www.it.fht-esslingen.de/~schmidt/vorlesungen/kryptologie/seminar/ws9798/html/prim/prim-1.html>
163
165 Steven Schubiger <schubiger@cpan.org>
166
168 This program is free software; you may redistribute it and/or modify it
169 under the same terms as Perl itself.
170 See <http://dev.perl.org/licenses/>
172perl v5.34.0 2021-07-22 Math::Prime::XS(3)