| 1 | # Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2018, 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 | |||||||||||||||||||||||||||||||||||
| 19 | # values_type => 'mod2' | ||||||||||||||||||||||||||||||||||
| 20 | |||||||||||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||||||||
| 22 | package Math::NumSeq::PrimeFactorCount; | ||||||||||||||||||||||||||||||||||
| 23 | 8 | ▶ | use 5.004; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 24 | 8 | ▶ | use strict; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 25 | 8 | ▶ | use List::Util 'min', 'max'; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 26 | |||||||||||||||||||||||||||||||||||
| 27 | 8 | ▶ | use vars '$VERSION','@ISA'; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 28 | 8 | $VERSION = 75; | |||||||||||||||||||||||||||||||||
| 29 | |||||||||||||||||||||||||||||||||||
| 30 | 8 | ▶ | use Math::NumSeq; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 31 | 8 | ▶ | use Math::NumSeq::Base::IterateIth; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 32 | 8 | @ISA = ('Math::NumSeq::Base::IterateIth', | |||||||||||||||||||||||||||||||||
| 33 | 'Math::NumSeq'); | ||||||||||||||||||||||||||||||||||
| 34 | 8 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||||||||
| 35 | |||||||||||||||||||||||||||||||||||
| 36 | 8 | ▶ | use Math::Prime::XS 'is_prime'; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 37 | 8 | ▶ | use Math::Factor::XS 'prime_factors'; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 38 | |||||||||||||||||||||||||||||||||||
| 39 | 8 | ▶ | use Math::NumSeq::Fibonacci; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 40 | 8 | *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate; | |||||||||||||||||||||||||||||||||
| 41 | |||||||||||||||||||||||||||||||||||
| 42 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||||||||
| 43 | #use Smart::Comments; | ||||||||||||||||||||||||||||||||||
| 44 | |||||||||||||||||||||||||||||||||||
| 45 | |||||||||||||||||||||||||||||||||||
| 46 | # cf. Untouchables, not sum of proper divisors of any other integer | ||||||||||||||||||||||||||||||||||
| 47 | # p*q sum S=1+p+q | ||||||||||||||||||||||||||||||||||
| 48 | # so sums up to hi need factorize to (hi^2)/4 | ||||||||||||||||||||||||||||||||||
| 49 | # | ||||||||||||||||||||||||||||||||||
| 50 | |||||||||||||||||||||||||||||||||||
| 51 | 8 | ▶ | use constant values_min => 0; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 52 | 8 | ▶ | use constant i_start => 1; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 53 | |||||||||||||||||||||||||||||||||||
| 54 | 0 | ▶ | sub values_max { | ||||||||||||||||||||||||||||||||
|
Subroutine
values_max: not called CC=2 SCAR=17.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 55 | 0 | my ($self) = @_; | |||||||||||||||||||||||||||||||||
| 56 | 0 | ▶ | if ($self->{'values_type'} eq 'mod2') { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 57 | 0 | return 1; | |||||||||||||||||||||||||||||||||
| 58 | } else { | ||||||||||||||||||||||||||||||||||
| 59 | 0 | return undef; | |||||||||||||||||||||||||||||||||
| 60 | } | ||||||||||||||||||||||||||||||||||
| 61 | } | ||||||||||||||||||||||||||||||||||
| 62 | 8 | ▶ | use constant characteristic_count => 1; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 63 | 8 | ▶ | use constant characteristic_smaller => 1; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 64 | 8 | ▶ | use constant characteristic_increasing => 0; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 65 | |||||||||||||||||||||||||||||||||||
| 66 | 8 | ▶ | use constant parameter_info_array => | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 67 | [ | ||||||||||||||||||||||||||||||||||
| 68 | { name => 'prime_type', | ||||||||||||||||||||||||||||||||||
| 69 | display => Math::NumSeq::__('Prime Type'), | ||||||||||||||||||||||||||||||||||
| 70 | type => 'enum', | ||||||||||||||||||||||||||||||||||
| 71 | default => 'all', | ||||||||||||||||||||||||||||||||||
| 72 | choices => ['all','odd','4k+1','4k+3', | ||||||||||||||||||||||||||||||||||
| 73 | 'twin','SG','safe'], | ||||||||||||||||||||||||||||||||||
| 74 | choices_display => [Math::NumSeq::__('All'), | ||||||||||||||||||||||||||||||||||
| 75 | Math::NumSeq::__('Odd'), | ||||||||||||||||||||||||||||||||||
| 76 | # TRANSLATORS: "4k+1" meaning numbers 1,5,9,13 etc, probably no need to translate except into another script if Latin letter "k" won't be recognised | ||||||||||||||||||||||||||||||||||
| 77 | Math::NumSeq::__('4k+1'), | ||||||||||||||||||||||||||||||||||
| 78 | Math::NumSeq::__('4k+3'), | ||||||||||||||||||||||||||||||||||
| 79 | Math::NumSeq::__('Twin'), | ||||||||||||||||||||||||||||||||||
| 80 | Math::NumSeq::__('SG'), | ||||||||||||||||||||||||||||||||||
| 81 | Math::NumSeq::__('Safe'), | ||||||||||||||||||||||||||||||||||
| 82 | ], | ||||||||||||||||||||||||||||||||||
| 83 | description => Math::NumSeq::__('The type of primes to count. | ||||||||||||||||||||||||||||||||||
| 84 | twin=P where P+2 or P-2 also prime. | ||||||||||||||||||||||||||||||||||
| 85 | SG=Sophie Germain P where 2P+1 also prime. | ||||||||||||||||||||||||||||||||||
| 86 | safe=P where (P-1)/2 also prime (the "other" of the SGs).'), | ||||||||||||||||||||||||||||||||||
| 87 | }, | ||||||||||||||||||||||||||||||||||
| 88 | { name => 'multiplicity', | ||||||||||||||||||||||||||||||||||
| 89 | display => Math::NumSeq::__('Multiplicity'), | ||||||||||||||||||||||||||||||||||
| 90 | type => 'enum', | ||||||||||||||||||||||||||||||||||
| 91 | default => 'repeated', | ||||||||||||||||||||||||||||||||||
| 92 | choices => ['repeated','distinct'], | ||||||||||||||||||||||||||||||||||
| 93 | choices_display => [Math::NumSeq::__('Repeated'), | ||||||||||||||||||||||||||||||||||
| 94 | Math::NumSeq::__('Distinct'), | ||||||||||||||||||||||||||||||||||
| 95 | ], | ||||||||||||||||||||||||||||||||||
| 96 | description => Math::NumSeq::__('Whether to include repeated prime factors, or only distinct prime factors.'), | ||||||||||||||||||||||||||||||||||
| 97 | }, | ||||||||||||||||||||||||||||||||||
| 98 | |||||||||||||||||||||||||||||||||||
| 99 | # not documented yet | ||||||||||||||||||||||||||||||||||
| 100 | { name => 'values_type', | ||||||||||||||||||||||||||||||||||
| 101 | share_key => 'values_type_cm2', | ||||||||||||||||||||||||||||||||||
| 102 | display => Math::NumSeq::__('Values Type'), | ||||||||||||||||||||||||||||||||||
| 103 | type => 'enum', | ||||||||||||||||||||||||||||||||||
| 104 | default => 'count', | ||||||||||||||||||||||||||||||||||
| 105 | choices => ['count','mod2'], | ||||||||||||||||||||||||||||||||||
| 106 | choices_display => [Math::NumSeq::__('Count'), | ||||||||||||||||||||||||||||||||||
| 107 | Math::NumSeq::__('Mod2'), | ||||||||||||||||||||||||||||||||||
| 108 | ], | ||||||||||||||||||||||||||||||||||
| 109 | # description => Math::NumSeq::__('...'), | ||||||||||||||||||||||||||||||||||
| 110 | }, | ||||||||||||||||||||||||||||||||||
| 111 | 8 | ]; | |||||||||||||||||||||||||||||||||
| 112 | |||||||||||||||||||||||||||||||||||
| 113 | 12 | ▶ | sub description { | ||||||||||||||||||||||||||||||||
|
Subroutine
description: called CC=9 SCAR=22.7
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 114 | 12 | my ($self) = @_; | |||||||||||||||||||||||||||||||||
| 115 | 12 | ▶ | if (ref $self) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 116 | return ($self->{'multiplicity'} eq 'repeated' | ||||||||||||||||||||||||||||||||||
| 117 | ? Math::NumSeq::__('Count of prime factors, including repetitions.') | ||||||||||||||||||||||||||||||||||
| 118 | : Math::NumSeq::__('Count of distinct prime factors.')) | ||||||||||||||||||||||||||||||||||
| 119 | . ($self->{'prime_type'} eq 'odd' ? "\nOdd primes only." | ||||||||||||||||||||||||||||||||||
| 120 | : $self->{'prime_type'} eq '4k+1' ? "\nPrimes of form 4k+1 only." | ||||||||||||||||||||||||||||||||||
| 121 | : $self->{'prime_type'} eq '4k+3' ? "\nPrimes of form 4k+3 only." | ||||||||||||||||||||||||||||||||||
| 122 | : $self->{'prime_type'} eq 'twin' ? "\nTwin primes only." | ||||||||||||||||||||||||||||||||||
| 123 | : $self->{'prime_type'} eq 'SG' ? "\nSophie Germain primes only (2P+1 also prime)." | ||||||||||||||||||||||||||||||||||
| 124 | 6 | ▶ | : $self->{'prime_type'} eq 'SG' ? "\nSafe primes only ((P-1)/2 also prime)." | ||||||||||||||||||||||||||||||||
|
Branch: 7 branches
| |||||||||||||||||||||||||||||||||||
| 125 | : ""); | ||||||||||||||||||||||||||||||||||
| 126 | } else { | ||||||||||||||||||||||||||||||||||
| 127 | # class method | ||||||||||||||||||||||||||||||||||
| 128 | 6 | return Math::NumSeq::__('Count of prime factors.'); | |||||||||||||||||||||||||||||||||
| 129 | } | ||||||||||||||||||||||||||||||||||
| 130 | } | ||||||||||||||||||||||||||||||||||
| 131 | |||||||||||||||||||||||||||||||||||
| 132 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||||||||
| 133 | # | ||||||||||||||||||||||||||||||||||
| 134 | # count 1-bits in exponents of primes | ||||||||||||||||||||||||||||||||||
| 135 | # A000028,A000379 seqs | ||||||||||||||||||||||||||||||||||
| 136 | # A133008 characteristic | ||||||||||||||||||||||||||||||||||
| 137 | # A131181,A026416 same, but 1 in "B" class | ||||||||||||||||||||||||||||||||||
| 138 | # A064547 count 1 bits in prime exponents | ||||||||||||||||||||||||||||||||||
| 139 | # A066724 so a(i)*a(j) not in seq | ||||||||||||||||||||||||||||||||||
| 140 | # A026477 so a(i)*a(j)*a(k) not in seq | ||||||||||||||||||||||||||||||||||
| 141 | # A050376 prime^(2^k) | ||||||||||||||||||||||||||||||||||
| 142 | # A084400 smallest not dividing product a(1)..a(n-1), is prime^(2^k) | ||||||||||||||||||||||||||||||||||
| 143 | |||||||||||||||||||||||||||||||||||
| 144 | 8 | my %oeis_anum = (repeated => { all => 'A001222', | |||||||||||||||||||||||||||||||||
| 145 | odd => 'A087436', | ||||||||||||||||||||||||||||||||||
| 146 | '4k+1' => 'A083025', | ||||||||||||||||||||||||||||||||||
| 147 | '4k+3' => 'A065339', | ||||||||||||||||||||||||||||||||||
| 148 | }, | ||||||||||||||||||||||||||||||||||
| 149 | distinct => { all => 'A001221', | ||||||||||||||||||||||||||||||||||
| 150 | odd => 'A005087', | ||||||||||||||||||||||||||||||||||
| 151 | '4k+1' => 'A005089', | ||||||||||||||||||||||||||||||||||
| 152 | '4k+3' => 'A005091', | ||||||||||||||||||||||||||||||||||
| 153 | twin => 'A284203', | ||||||||||||||||||||||||||||||||||
| 154 | SG => 'A156542', | ||||||||||||||||||||||||||||||||||
| 155 | }, | ||||||||||||||||||||||||||||||||||
| 156 | ); | ||||||||||||||||||||||||||||||||||
| 157 | # OEIS-Catalogue: A001222 | ||||||||||||||||||||||||||||||||||
| 158 | # OEIS-Catalogue: A087436 prime_type=odd | ||||||||||||||||||||||||||||||||||
| 159 | # OEIS-Catalogue: A083025 prime_type=4k+1 | ||||||||||||||||||||||||||||||||||
| 160 | # OEIS-Catalogue: A065339 prime_type=4k+3 | ||||||||||||||||||||||||||||||||||
| 161 | |||||||||||||||||||||||||||||||||||
| 162 | # OEIS-Catalogue: A001221 multiplicity=distinct | ||||||||||||||||||||||||||||||||||
| 163 | # OEIS-Catalogue: A005087 multiplicity=distinct prime_type=odd | ||||||||||||||||||||||||||||||||||
| 164 | # OEIS-Catalogue: A005089 multiplicity=distinct prime_type=4k+1 | ||||||||||||||||||||||||||||||||||
| 165 | # OEIS-Catalogue: A005091 multiplicity=distinct prime_type=4k+3 | ||||||||||||||||||||||||||||||||||
| 166 | # OEIS-Catalogue: A284203 multiplicity=distinct prime_type=twin | ||||||||||||||||||||||||||||||||||
| 167 | # OEIS-Catalogue: A156542 multiplicity=distinct prime_type=SG | ||||||||||||||||||||||||||||||||||
| 168 | |||||||||||||||||||||||||||||||||||
| 169 | 6 | ▶ | sub oeis_anum { | ||||||||||||||||||||||||||||||||
|
Subroutine
oeis_anum: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 170 | 6 | my ($self) = @_; | |||||||||||||||||||||||||||||||||
| 171 | 6 | return $oeis_anum{$self->{'multiplicity'}}->{$self->{'prime_type'}}; | |||||||||||||||||||||||||||||||||
| 172 | } | ||||||||||||||||||||||||||||||||||
| 173 | |||||||||||||||||||||||||||||||||||
| 174 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||||||||
| 175 | |||||||||||||||||||||||||||||||||||
| 176 | # prime_factors() is about 5x faster | ||||||||||||||||||||||||||||||||||
| 177 | # | ||||||||||||||||||||||||||||||||||
| 178 | 2014 | ▶ | sub ith { | ||||||||||||||||||||||||||||||||
|
Subroutine
ith: called CC=18 SCAR=28.9
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 179 | 2014 | my ($self, $i) = @_; | |||||||||||||||||||||||||||||||||
| 180 | 2014 | $i = abs($i); | |||||||||||||||||||||||||||||||||
| 181 | |||||||||||||||||||||||||||||||||||
| 182 | 2014 | my ($good, @primes) = _prime_factors($i); | |||||||||||||||||||||||||||||||||
| 183 | 2014 | ▶ | return undef unless $good; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 184 | |||||||||||||||||||||||||||||||||||
| 185 | 2014 | my $multiplicity = ($self->{'multiplicity'} ne 'distinct'); | |||||||||||||||||||||||||||||||||
| 186 | 2014 | my $prime_type = $self->{'prime_type'}; | |||||||||||||||||||||||||||||||||
| 187 | 2014 | my $count = 0; | |||||||||||||||||||||||||||||||||
| 188 | |||||||||||||||||||||||||||||||||||
| 189 | 2014 | ▶ | while (@primes) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 190 | 2858 | my $p = shift @primes; | |||||||||||||||||||||||||||||||||
| 191 | 2858 | my $c = 1; | |||||||||||||||||||||||||||||||||
| 192 | 2858 | ▶ | while (@primes && $primes[0] == $p) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
@primes and $primes[0] == $p
MC/DC100%2/2
@primes and $primes[0] == $p
@primes
$primes[0] == $p
Truth table100%3/3
A and B
A= @primesB= $primes[0] == $p
| |||||||||||||||||||||||||||||||||||
| 193 | 1003 | shift @primes; | |||||||||||||||||||||||||||||||||
| 194 | 1003 | $c += $multiplicity; | |||||||||||||||||||||||||||||||||
| 195 | } | ||||||||||||||||||||||||||||||||||
| 196 | |||||||||||||||||||||||||||||||||||
| 197 | 2858 | ▶ | if ($prime_type eq 'odd') { | ||||||||||||||||||||||||||||||||
|
Branch: 6 branches
| |||||||||||||||||||||||||||||||||||
| 198 | 86 | ▶ | next unless $p & 1; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 199 | } elsif ($prime_type eq '4k+1') { | ||||||||||||||||||||||||||||||||||
| 200 | 86 | ▶ | next unless ($p&3)==1; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 201 | } elsif ($prime_type eq '4k+3') { | ||||||||||||||||||||||||||||||||||
| 202 | 86 | ▶ | next unless ($p&3)==3; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 203 | } elsif ($prime_type eq 'twin') { | ||||||||||||||||||||||||||||||||||
| 204 | 1212 | ▶ | next unless _is_twin_prime($p); | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 205 | } elsif ($prime_type eq 'SG') { | ||||||||||||||||||||||||||||||||||
| 206 | 567 | ▶ | next unless _is_SG_prime($p); | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 207 | } elsif ($prime_type eq 'safe') { | ||||||||||||||||||||||||||||||||||
| 208 | 567 | ▶ | next unless _is_safe_prime($p); | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 209 | |||||||||||||||||||||||||||||||||||
| 210 | # } elsif ($prime_type eq 'twin_first') { | ||||||||||||||||||||||||||||||||||
| 211 | # next unless is_prime($p+2); | ||||||||||||||||||||||||||||||||||
| 212 | # } elsif ($prime_type eq 'twin_second') { | ||||||||||||||||||||||||||||||||||
| 213 | # next unless is_prime($p-2); | ||||||||||||||||||||||||||||||||||
| 214 | } | ||||||||||||||||||||||||||||||||||
| 215 | 1767 | $count += $c; | |||||||||||||||||||||||||||||||||
| 216 | } | ||||||||||||||||||||||||||||||||||
| 217 | |||||||||||||||||||||||||||||||||||
| 218 | 2014 | ▶ | if ($self->{'values_type'} eq 'mod2') { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 219 | 0 | $count %= 2; | |||||||||||||||||||||||||||||||||
| 220 | } | ||||||||||||||||||||||||||||||||||
| 221 | 2014 | return $count; | |||||||||||||||||||||||||||||||||
| 222 | } | ||||||||||||||||||||||||||||||||||
| 223 | |||||||||||||||||||||||||||||||||||
| 224 | # Return ($good, $prime,$prime,$prime,...). | ||||||||||||||||||||||||||||||||||
| 225 | # $good is true if a full factorization is found. | ||||||||||||||||||||||||||||||||||
| 226 | # $good is false if cannot factorize because $n is too big or infinite. | ||||||||||||||||||||||||||||||||||
| 227 | # | ||||||||||||||||||||||||||||||||||
| 228 | # If $n==0 or $n==1 then there are no prime factors and the return is | ||||||||||||||||||||||||||||||||||
| 229 | # $good=1 and an empty list of primes. | ||||||||||||||||||||||||||||||||||
| 230 | # | ||||||||||||||||||||||||||||||||||
| 231 | 6191 | ▶ | sub _prime_factors { | ||||||||||||||||||||||||||||||||
|
Subroutine
_prime_factors: called CC=12 SCAR=44.2
| |||||||||||||||||||||||||||||||||||
| 232 | 6191 | my ($n) = @_; | |||||||||||||||||||||||||||||||||
| 233 | ### _prime_factors(): $n | ||||||||||||||||||||||||||||||||||
| 234 | |||||||||||||||||||||||||||||||||||
| 235 | 6191 | ▶ | unless ($n >= 0) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 236 | 9 | return 0; | |||||||||||||||||||||||||||||||||
| 237 | } | ||||||||||||||||||||||||||||||||||
| 238 | 6182 | ▶ | if (_is_infinite($n)) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 239 | 0 | return 0; | |||||||||||||||||||||||||||||||||
| 240 | } | ||||||||||||||||||||||||||||||||||
| 241 | |||||||||||||||||||||||||||||||||||
| 242 | 6182 | ▶ | if ($n <= 0xFFFF_FFFF) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 243 | 6182 | return (1, prime_factors($n)); | |||||||||||||||||||||||||||||||||
| 244 | } | ||||||||||||||||||||||||||||||||||
| 245 | |||||||||||||||||||||||||||||||||||
| 246 | 0 | my @ret; | |||||||||||||||||||||||||||||||||
| 247 | 0 | ▶ | until ($n % 2) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 248 | ### div2: $n | ||||||||||||||||||||||||||||||||||
| 249 | 0 | $n /= 2; | |||||||||||||||||||||||||||||||||
| 250 | 0 | push @ret, 2; | |||||||||||||||||||||||||||||||||
| 251 | } | ||||||||||||||||||||||||||||||||||
| 252 | |||||||||||||||||||||||||||||||||||
| 253 | # Stop at when prime $p reaches $limit and when no prime factor has been | ||||||||||||||||||||||||||||||||||
| 254 | # found for the last 20 attempted $p. Stopping only after a run of no | ||||||||||||||||||||||||||||||||||
| 255 | # factors found allows big primorials 2*3*5*7*13*... to be divided out. | ||||||||||||||||||||||||||||||||||
| 256 | # If the divisions are making progress reducing $i then continue. | ||||||||||||||||||||||||||||||||||
| 257 | # | ||||||||||||||||||||||||||||||||||
| 258 | # Would like $p and $gap to count primes, not just odd numbers. Perhaps | ||||||||||||||||||||||||||||||||||
| 259 | # a table of small primes. The first gap of 36 odds between primes | ||||||||||||||||||||||||||||||||||
| 260 | # occurs at prime=31469. cf A000230 smallest prime p for gap 2n. | ||||||||||||||||||||||||||||||||||
| 261 | |||||||||||||||||||||||||||||||||||
| 262 | 0 | ▶ | my $limit = 10_000 / (_blog2_estimate($n) || 1); | ||||||||||||||||||||||||||||||||
|
Condition0%0/2
_blog2_estimate($n) || 1
MC/DC0%0/1
_blog2_estimate($n) || 1
_blog2_estimate($n)
Truth table0%0/2
A
A= _blog2_estimate($n)
| |||||||||||||||||||||||||||||||||||
| 263 | 0 | my $gap = 0; | |||||||||||||||||||||||||||||||||
| 264 | 0 | ▶ | for (my $p = 3; $gap < 36 || $p <= $limit ; $p += 2) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
$gap < 36 or $p <= $limit
MC/DC0%0/2
$gap < 36 or $p <= $limit
$gap < 36
$p <= $limit
Truth table0%0/3
A or B
A= $gap < 36B= $p <= $limit
| |||||||||||||||||||||||||||||||||||
| 265 | 0 | ▶ | if ($n % $p) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 266 | 0 | $gap++; | |||||||||||||||||||||||||||||||||
| 267 | } else { | ||||||||||||||||||||||||||||||||||
| 268 | 0 | ▶ | do { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 269 | ### prime: $p | ||||||||||||||||||||||||||||||||||
| 270 | 0 | $n /= $p; | |||||||||||||||||||||||||||||||||
| 271 | 0 | push @ret, $p; | |||||||||||||||||||||||||||||||||
| 272 | } until ($n % $p); | ||||||||||||||||||||||||||||||||||
| 273 | |||||||||||||||||||||||||||||||||||
| 274 | 0 | ▶ | if ($n <= 1) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 275 | ### all factors found ... | ||||||||||||||||||||||||||||||||||
| 276 | 0 | return (1, @ret); | |||||||||||||||||||||||||||||||||
| 277 | } | ||||||||||||||||||||||||||||||||||
| 278 | 0 | ▶ | if ($n < 0xFFFF_FFFF) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 279 | ### remaining factors by XS ... | ||||||||||||||||||||||||||||||||||
| 280 | 0 | return (1, @ret, prime_factors($n)); | |||||||||||||||||||||||||||||||||
| 281 | } | ||||||||||||||||||||||||||||||||||
| 282 | 0 | $gap = 0; | |||||||||||||||||||||||||||||||||
| 283 | } | ||||||||||||||||||||||||||||||||||
| 284 | } | ||||||||||||||||||||||||||||||||||
| 285 | 0 | return 0; # factors too big | |||||||||||||||||||||||||||||||||
| 286 | } | ||||||||||||||||||||||||||||||||||
| 287 | |||||||||||||||||||||||||||||||||||
| 288 | 1212 | ▶ | sub _is_twin_prime { | ||||||||||||||||||||||||||||||||
|
Subroutine
_is_twin_prime: called CC=2 SCAR=6.9
| |||||||||||||||||||||||||||||||||||
| 289 | 1212 | my ($n) = @_; | |||||||||||||||||||||||||||||||||
| 290 | ### assert: $n >= 2 | ||||||||||||||||||||||||||||||||||
| 291 | ### assert: is_prime($n) | ||||||||||||||||||||||||||||||||||
| 292 | 1212 | ▶ | return (is_prime($n+2) || is_prime($n-2)); | ||||||||||||||||||||||||||||||||
|
Condition100%3/3
is_prime($n + 2) || is_prime($n - 2)
MC/DC100%2/2
is_prime($n + 2) || is_prime($n - 2)
is_prime($n + 2)
is_prime($n - 2)
Truth table100%3/3
A || B
A= is_prime($n + 2)B= is_prime($n - 2)
| |||||||||||||||||||||||||||||||||||
| 293 | } | ||||||||||||||||||||||||||||||||||
| 294 | 567 | ▶ | sub _is_SG_prime { | ||||||||||||||||||||||||||||||||
|
Subroutine
_is_SG_prime: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 295 | 567 | my ($n) = @_; | |||||||||||||||||||||||||||||||||
| 296 | ### assert: is_prime($n) | ||||||||||||||||||||||||||||||||||
| 297 | 567 | return is_prime(2*$n+1); | |||||||||||||||||||||||||||||||||
| 298 | } | ||||||||||||||||||||||||||||||||||
| 299 | 567 | ▶ | sub _is_safe_prime { | ||||||||||||||||||||||||||||||||
|
Subroutine
_is_safe_prime: called CC=2 SCAR=6.9
| |||||||||||||||||||||||||||||||||||
| 300 | 567 | my ($n) = @_; | |||||||||||||||||||||||||||||||||
| 301 | ### assert: is_prime($n) | ||||||||||||||||||||||||||||||||||
| 302 | 567 | ▶ | return (($n&1) && is_prime(($n-1)/2)); | ||||||||||||||||||||||||||||||||
|
Condition100%3/3
$n & 1 && is_prime(($n - 1) / 2)
MC/DC100%2/2
$n & 1 && is_prime(($n - 1) / 2)
$n & 1
is_prime(($n - 1) / 2)
Truth table100%3/3
A && B
A= $n & 1B= is_prime(($n - 1) / 2)
| |||||||||||||||||||||||||||||||||||
| 303 | } | ||||||||||||||||||||||||||||||||||
| 304 | |||||||||||||||||||||||||||||||||||
| 305 | 110 | ▶ | sub pred { | ||||||||||||||||||||||||||||||||
|
Subroutine
pred: called CC=2 SCAR=8.1
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 306 | 110 | my ($self, $value) = @_; | |||||||||||||||||||||||||||||||||
| 307 | 110 | ▶ | return ($value >= 0 && $value == int($value)); | ||||||||||||||||||||||||||||||||
|
Condition33%1/3
$value >= 0 && $value == int $value
MC/DC0%0/2
$value >= 0 && $value == int $value
$value >= 0
$value == int $value
Truth table33%1/3
A && B
A= $value >= 0B= $value == int $value
| |||||||||||||||||||||||||||||||||||
| 308 | } | ||||||||||||||||||||||||||||||||||
| 309 | |||||||||||||||||||||||||||||||||||
| 310 | 8 | 1; | |||||||||||||||||||||||||||||||||
| 311 | __END__ | ||||||||||||||||||||||||||||||||||