1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
#!/usr/bin/env perl
use strict;
use warnings;
use Test::More;
use Math::Prime::Util::GMP qw/prime_count prime_count_lower prime_count_upper/;
my %pivals = (
1 => 0,
10 => 4,
100 => 25,
1000 => 168,
10000 => 1229,
65535 => 6542,
);
# Generated with:
# perl -Mbigint -MMath::Prime::Util -E 'foreach my $e (64 .. 120) { my $start = 2**$e + int(rand(2**($e-1))); my $end = $start + int(rand(2000)); my $c = Math::Prime::Util::PP::prime_count($start, $end); say " [\"$start\", \"$end\", $c]," }'
my @tests = (
["24113483758197309440", "24113483758197310396", 23],
["45490240575506677760", "45490240575506679266", 45],
["75458848506302300160", "75458848506302301114", 18],
["161891136728481923072", "161891136728481923850", 18],
["342679779996280025856", "342679779996280027487", 36],
["759817770139002651712", "759817770139002652700", 26],
["1747599191389174303424", "1747599191389174303464", 1],
["3277252439479060606848", "3277252439479060607688", 12],
["6887003433586725213696", "6887003433586725213705", 0],
["9515645314265862127392", "9515645314265862128163", 15],
["26114788673620260854784", "26114788673620260855763", 17],
["50021095190478561709568", "50021095190478561710552", 16],
["99293609391529723419136", "99293609391529723420902", 20],
["192328541043198946838272", "192328541043198946839023", 18],
["386730387965240293676544", "386730387965240293678117", 29],
["735479117913496587353088", "735479117913496587354687", 32],
["1330998807397722174706176", "1330998807397722174706347", 3],
["2904510561226220349412352", "2904510561226220349413930", 21],
["6847845859597286698824704", "6847845859597286698826460", 26],
["9880100064397462397649408", "9880100064397462397650566", 17],
["27282839498809356795298816", "27282839498809356795300564", 23],
["41281035060688503590597632", "41281035060688503590598867", 15],
["90374604407955267181195264", "90374604407955267181195457", 2],
["200915297903707834362390528", "200915297903707834362391737", 22],
["407168505212786768724781056", "407168505212786768724782199", 16],
["817226365950024137449562112", "817226365950024137449563070", 14],
["1621795554319024274899124224", "1621795554319024274899125678", 18],
["3660769329531840549798248448", "3660769329531840549798250278", 23],
["7314734077273801099596496896", "7314734077273801099596498034", 16],
["10921064834678012199192993792", "10921064834678012199192994171", 5],
["24344155473536054398385987584", "24344155473536054398385988831", 14],
["46348470312928428796771975168", "46348470312928428796771976813", 28],
["90920702154966737593543950336", "90920702154966737593543951561", 19],
["233651247954773375187087900672", "233651247954773375187087901872", 16],
["396231658265327350374175801344", "396231658265327350374175803015", 25],
["734317226076915700748351602688", "734317226076915700748351602878", 0],
["1696551122155337401496703205376", "1696551122155337401496703205528", 1],
["3100618561736693802993406410752", "3100618561736693802993406411961", 22],
["6306554584349917605986812821504", "6306554584349917605986812822041", 9],
["12897043632271155211973625643008", "12897043632271155211973625643214", 3],
["27070533331838590423947251286016", "27070533331838590423947251286519", 5],
["44933719679228300847894502572032", "44933719679228300847894502574007", 26],
["92067632902534481695789005144064", "92067632902534481695789005144486", 7],
["219741981610812063391578010288128", "219741981610812063391578010289366", 22],
["441164516482197726783156020576256", "441164516482197726783156020576737", 5],
["783694033185045453566312041152512", "783694033185045453566312041152692", 1],
["1754258052575393907132624082305024", "1754258052575393907132624082305337", 4],
["3291172491135828814265248164610048", "3291172491135828814265248164611897", 21],
["5255505796082429028530496329220096", "5255505796082429028530496329221910", 27],
["12176969828012415257060992658440192", "12176969828012415257060992658440427", 5],
["22889636161029770514121985316880384", "22889636161029770514121985316881826", 17],
["44359130889092671028243970633760768", "44359130889092671028243970633762444", 17],
["94248617103459242056487941267521536", "94248617103459242056487941267522522", 16],
["191861723074481884112975882535043072", "191861723074481884112975882535043603", 10],
["396766049747924068225951765070086144", "396766049747924068225951765070087394", 10],
["884985931172514936451903530140172288", "884985931172514936451903530140172881", 9],
["1969978340430920872903807060280344576", "1969978340430920872903807060280346393", 17],
);
my %pi2n = (
1 => '1',
2 => '2',
3 => '4',
4 => '6',
5 => '11',
6 => '18',
7 => '31',
8 => '54',
9 => '97',
10 => '172',
11 => '309',
12 => '564',
13 => '1028',
14 => '1900',
15 => '3512',
16 => '6542',
17 => '12251',
18 => '23000',
19 => '43390',
20 => '82025',
21 => '155611',
22 => '295947',
23 => '564163',
24 => '1077871',
25 => '2063689',
26 => '3957809',
27 => '7603553',
28 => '14630843',
29 => '28192750',
30 => '54400028',
31 => '105097565',
32 => '203280221',
33 => '393615806',
34 => '762939111',
35 => '1480206279',
36 => '2874398515',
37 => '5586502348',
38 => '10866266172',
39 => '21151907950',
40 => '41203088796',
41 => '80316571436',
42 => '156661034233',
43 => '305761713237',
44 => '597116381732',
45 => '1166746786182',
46 => '2280998753949',
47 => '4461632979717',
48 => '8731188863470',
49 => '17094432576778',
50 => '33483379603407',
51 => '65612899915304',
52 => '128625503610475',
53 => '252252704148404',
54 => '494890204904784',
55 => '971269945245201',
56 => '1906879381028850',
57 => '3745011184713964',
58 => '7357400267843990',
59 => '14458792895301660',
60 => '28423094496953330',
61 => '55890484045084135',
62 => '109932807585469973',
63 => '216289611853439384',
64 => '425656284035217743',
65 => '837903145466607212',
66 => '1649819700464785589',
67 => '3249254387052557215',
68 => '6400771597544937806',
69 => '12611864618760352880',
70 => '24855455363362685793',
71 => '48995571600129458363',
72 => '96601075195075186855',
73 => '190499823401327905601',
74 => '375744164937699609596',
75 => '741263521140740113483',
76 => '1462626667154509638735',
77 => '2886507381056867953916',
78 => '5697549648954257752872',
79 => '11248065615133675809379',
80 => '22209558889635384205844',
81 => '43860397052947409356492',
82 => '86631124695994360074872',
83 => '171136408646923240987028',
84 => '338124238545210097236684',
85 => '668150111666935905701562',
86 => '1320486952377516565496055',
);
plan tests => 4 + scalar (keys %pivals) + scalar @tests + 2*scalar(keys %pi2n);
# TODO: error cases
is( prime_count(0,1), 0, "prime_count(0,1) == 0");
is( prime_count(0,2), 1, "prime_count(0,2) == 1");
is( prime_count(0,3), 2, "prime_count(0,3) == 2");
is( prime_count(2,2), 1, "prime_count(2,2) == 2");
while (my($n, $pin) = each (%pivals)) {
is( prime_count(2, $n), $pin, "Pi($n) = $pin" );
}
foreach my $t (@tests) {
is( prime_count($t->[0], $t->[1]),
$t->[2],
"prime_count($t->[0],$t->[1]) = $t->[2]" );
}
while (my($n, $pin) = each (%pi2n)) {
use bigint;
cmp_ok( prime_count_lower(2 ** $n), '<=', $pin, "prime_count_lower(2^$n) <= $pin" );
cmp_ok( prime_count_upper(2 ** $n), '>=', $pin, "prime_count_upper(2^$n) >= $pin" );
}
|
