NumSeq/Primes.pm

filter: Statementstmt 93.9% 93 / 99 Branchbran 75.0% 18 / 24 Conditioncond 83.3% 5 / 6 MC/DCmcdc 75.0% 3 / 4 Subroutinesub 100% 20 / 20 Podpod 100% 4 / 4 totaltotal 91.0% 143 / 157 CC 15 SCAR 11.6
CC
15
Cov
90%
next
6.3
_primes_list
5.3
pred
5.0
CRAP 3.2
« NumSeq/CullenNumbers.pm ↑ Summary NumSeq/GolombSequence.pm »
1 # Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde
2  
3 # This file is part of Math-NumSeq.
4 #
5 # Math-NumSeq is free software; you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License as published by the
7 # Free Software Foundation; either version 3, or (at your option) any later
8 # version.
9 #
10 # Math-NumSeq is distributed in the hope that it will be useful, but
11 # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 # for more details.
14 #
15 # You should have received a copy of the GNU General Public License along
16 # with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.
17  
18 package Math::NumSeq::Primes;
19 11 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
20 11 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
21 11 ▶use POSIX ();
Subroutine BEGIN: called CC=1 SCAR=0.0
22 11 ▶use Math::Prime::XS 0.23 'is_prime'; # version 0.23 fix for 1928099
Subroutine BEGIN: called CC=1 SCAR=0.0
23  
24 11 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
25 11 $VERSION = 75;
26 11 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
27 11 @ISA = ('Math::NumSeq');
28 11 *_is_infinite = \&Math::NumSeq::_is_infinite;
29  
30 # uncomment this to run the ### lines
31 # use Smart::Comments;
32  
33  
34 # use constant name => Math::NumSeq::__('Prime Numbers');
35 11 ▶use constant description => Math::NumSeq::__('The prime numbers 2, 3, 5, 7, 11, 13, 17, etc.');
Subroutine BEGIN: called CC=1 SCAR=0.0
36 11 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
37 11 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
38 11 ▶use constant values_min => 2;
Subroutine BEGIN: called CC=1 SCAR=0.0
39 11 ▶use constant i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
40  
41 #------------------------------------------------------------------------------
42 # cf A010051 - characteristic boolean 0 or 1 according as N is prime
43 # A051006 characteristic as binary fraction, in decimal
44 # A051007 characteristic as binary fraction, continued fraction
45 # A000720 - pi(n) num primes <= n
46 # A018252 - the non-primes
47 # A002476 - primes 3k+1, which is also 6k+1
48 #
49 11 ▶use constant oeis_anum => 'A000040'; # primes
Subroutine BEGIN: called CC=1 SCAR=0.0
50  
51 #------------------------------------------------------------------------------
52  
53 11 ▶use constant 1.02; # for leading underscore
Subroutine BEGIN: called CC=1 SCAR=0.0
54 11 ▶use constant _MAX_PRIME_XS => do {
Subroutine BEGIN: called CC=1 SCAR=0.0
55 11 my $umax = POSIX::UINT_MAX() / 2;
56 # if ($umax > 0x8000_0000) {
57 # $umax = 0x8000_0000;
58 # }
59 11 $umax;
60 11 };
61  
62 98 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
63 98 my ($self) = @_;
64 98 $self->{'i'} = $self->i_start;
65 98 $self->{'array_lo'} = 1;
66 98 $self->{'array_hi'} = 1;
67 98 @{$self->{'array'}} = ();
68 }
69 # needs a prime_count() for arbitrary seek
70 #
71 # sub _UNTESTED__seek_to_value {
72 # my ($self, $value) = @_;
73 # my $array = $self->{'array'};
74 # if (@array) {
75 # if ($value >= $array->[0] && $value <= $array->[-1]) {
76 # # seek forward within $array
77 # while ($value > $array->[0]) {
78 # shift @$array;
79 # $self->{'i'}++;
80 # }
81 # return;
82 # }
83 # }
84 # $value = int($value);
85 # if ($value > _MAX_PRIME_XS) {
86 # # past limit
87 # $self->{'array'} = undef;
88 # return;
89 # }
90 # $self->{'i'} = _primes_count(0,$value);
91 # $self->{'array_lo'} = 0;
92 # $self->{'array_hi'} = $value-1;
93 # @{$self->{'array'}} = ();
94 # }
95  
96 1606 ▶sub next {
Subroutine next: called CC=6 SCAR=18.3
Pod documented
97 1606 my ($self) = @_;
98  
99 1606 ▶ while (! @{$self->{'array'}}) {
Branch: 1 branch
BranchTrueFalseTotal
unless (@{$self->{"array"};}) 85 1606 1691
100 # fill array
101 85 my $lo = $self->{'array_lo'};
102 85 my $hi = $self->{'array_hi'};
103  
104 85 $lo = $self->{'array_lo'} = $hi+1;
105 85 ▶ if ($lo > _MAX_PRIME_XS) {
Branch: 1 branch
BranchTrueFalseTotal
if ($lo > "2147483647.5") 0 85 85
106 0 return;
107 }
108  
109 85 my $len = int ($lo / 2);
110 85 ▶ if ($len > 100_000) {
Branch: 1 branch
BranchTrueFalseTotal
if ($len > 100000) 0 85 85
111 0 $len = 100_000;
112 }
113  
114 85 $hi = $lo + $len;
115 85 ▶ if ($hi < 500) {
Branch: 1 branch
BranchTrueFalseTotal
if ($hi < 500) 73 12 85
116 73 $hi = 500;
117 }
118 85 ▶ if ($hi > _MAX_PRIME_XS) {
Branch: 1 branch
BranchTrueFalseTotal
if ($hi > "2147483647.5") 0 85 85
119 0 $hi = _MAX_PRIME_XS;
120 }
121 85 $self->{'array_hi'} = $hi;
122  
123 85 @{$self->{'array'}} = _primes_list ($lo, $hi);
124 }
125 1606 return ($self->{'i'}++, shift @{$self->{'array'}});
126 }
127  
128  
129  
130 246 ▶sub _primes_list {
Subroutine _primes_list: called CC=4 SCAR=16.6
131 246 my ($lo, $hi) = @_;
132 ### _my_primes_list: "$lo to $hi"
133 246 ▶ if ($lo < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($lo < 0) 0 246 246
134 0 $lo = 0;
135 }
136 246 ▶ if ($hi > _MAX_PRIME_XS) {
Branch: 1 branch
BranchTrueFalseTotal
if ($hi > "2147483647.5") 0 246 246
137 0 $hi = _MAX_PRIME_XS;
138 }
139  
140 246 ▶ if ($hi < $lo) {
Branch: 1 branch
BranchTrueFalseTotal
if ($hi < $lo) 0 246 246
141 # Math::Prime::XS errors out if hi<lo
142 0 return;
143 }
144 246 return Math::Prime::XS::sieve_primes ($lo, $hi);
145 }
146  
147 5271 ▶sub pred {
Subroutine pred: called CC=5 SCAR=16.1
Pod documented
148 5271 my ($self, $value) = @_;
149 ### pred(): "$value"
150  
151 5271 ▶ if (_is_infinite($value) || $value > 0xFFFF_FFFF) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value) or $value > 4294967295) 2 5269 5271
Condition66%2/3
_is_infinite($value) or $value > 4294967295
l!l&&r!l&&!r
025269
MC/DC50%1/2
_is_infinite($value) or $value > 4294967295
_is_infinite($value) $value > 4294967295
Truth table66%2/3
A or B
A= _is_infinite($value)B= $value > 4294967295
ABresult
1X1
011
000
152 2 return undef;
153 }
154 5269 ▶ if ($value != int($value) || $value < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value != int $value or $value < 0) 2031 3238 5269
Condition100%3/3
$value != int $value or $value < 0
l!l&&r!l&&!r
202743238
MC/DC100%2/2
$value != int $value or $value < 0
$value != int $value $value < 0
Truth table100%3/3
A or B
A= $value != int $valueB= $value < 0
ABresult
1X1
011
000
155 2031 return 0;
156 }
157 3238 return is_prime($value);
158 }
159  
160 # sub ith {
161 # my ($self, $i) = @_;
162 # my $array = $self->{'array'};
163 # if ($i > $#$array) {
164 # my $hi = int ($i/log($i) * 2 + 5);
165 # do {
166 # $array = $self->{'array'} = [ undef, _my_primes_list (0, $hi) ];
167 # $hi *= 2;
168 # } while ($i > $#$array);
169 # }
170 # return $array->[$i];
171 # }
172  
173 11 ▶use Math::NumSeq::Fibonacci;
Subroutine BEGIN: called CC=1 SCAR=0.0
174 11 *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate;
175  
176 235 ▶sub value_to_i_estimate {
Subroutine value_to_i_estimate: called CC=3 SCAR=11.0
Pod documented
177 235 my ($self, $value) = @_;
178 ### value_to_i_estimate(): "$value"
179  
180 235 ▶ if ($value < 2) { return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 2) 83 152 235
181  
182 152 $value = int($value);
183 152 ▶ if (defined (my $blog2 = _blog2_estimate($value))) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $blog2 = _blog2_estimate($value))) 12 140 152
184 # est = v/log(v)
185 # log2(v) = log(v)/log(2)
186 # est = v/((log2(v)*log(2)))
187 # = v/log2(v) * 1/log(2)
188 # ~= v/log2(v) * 13/9
189 # ~= (13*v) / (9*log2(v))
190 # using 13/9 as an approximation to 1/log(2) to stay in BigInt
191 #
192 ### $blog2
193 ### num: $value*13
194 ### den: 9 * $blog2
195 12 return ($value * 13) / (9 * $blog2);
196 }
197  
198 ### log: log($value)
199 ### div: $value/log($value)
200 140 return int($value/log($value));
201 }
202  
203 11 1;
204 __END__
« NumSeq/CullenNumbers.pm ↑ Summary NumSeq/GolombSequence.pm »