| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 106 | 0 | return; | |||||||||||||||||||||||||||
| 107 | } | ||||||||||||||||||||||||||||
| 108 | |||||||||||||||||||||||||||||
| 109 | 85 | my $len = int ($lo / 2); | |||||||||||||||||||||||||||
| 110 | 85 | ▶ | if ($len > 100_000) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 111 | 0 | $len = 100_000; | |||||||||||||||||||||||||||
| 112 | } | ||||||||||||||||||||||||||||
| 113 | |||||||||||||||||||||||||||||
| 114 | 85 | $hi = $lo + $len; | |||||||||||||||||||||||||||
| 115 | 85 | ▶ | if ($hi < 500) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 116 | 73 | $hi = 500; | |||||||||||||||||||||||||||
| 117 | } | ||||||||||||||||||||||||||||
| 118 | 85 | ▶ | if ($hi > _MAX_PRIME_XS) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 134 | 0 | $lo = 0; | |||||||||||||||||||||||||||
| 135 | } | ||||||||||||||||||||||||||||
| 136 | 246 | ▶ | if ($hi > _MAX_PRIME_XS) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 137 | 0 | $hi = _MAX_PRIME_XS; | |||||||||||||||||||||||||||
| 138 | } | ||||||||||||||||||||||||||||
| 139 | |||||||||||||||||||||||||||||
| 140 | 246 | ▶ | if ($hi < $lo) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
Condition66%2/3
_is_infinite($value) or $value > 4294967295
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
| |||||||||||||||||||||||||||||
| 152 | 2 | return undef; | |||||||||||||||||||||||||||
| 153 | } | ||||||||||||||||||||||||||||
| 154 | 5269 | ▶ | if ($value != int($value) || $value < 0) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$value != int $value or $value < 0
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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 181 | |||||||||||||||||||||||||||||
| 182 | 152 | $value = int($value); | |||||||||||||||||||||||||||
| 183 | 152 | ▶ | if (defined (my $blog2 = _blog2_estimate($value))) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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__ | ||||||||||||||||||||||||||||