| line |
true |
false |
branch |
|
22
|
37 |
1196 |
if (n <= 1) return (n==1); |
|
23
|
62 |
1134 |
if (k <= 1) return 1; |
|
25
|
588 |
546 |
if (!(n&1)) { /* Check and remove all multiples of 2 */ |
|
26
|
348 |
240 |
if (n & ((UVCONST(1) << k)-1)) return 0; |
|
27
|
240 |
0 |
n >>= ctz(n); |
|
28
|
20 |
220 |
if (n == 1) return 1; |
|
31
|
0 |
766 |
if (k > MPU_MAX_POW3) return 0; |
|
35
|
470 |
296 |
if (k == 2) { |
|
36
|
160 |
310 |
if ( (!(n % 3) && (n % 9)) |
|
|
74 |
86 |
if ( (!(n % 3) && (n % 9)) |
|
37
|
118 |
266 |
|| (!(n % 5) && (n % 25)) |
|
|
72 |
46 |
|| (!(n % 5) && (n % 25)) |
|
38
|
50 |
288 |
|| (!(n % 7) && (n % 49)) |
|
|
18 |
32 |
|| (!(n % 7) && (n % 49)) |
|
39
|
28 |
278 |
|| (!(n % 11) && (n % 121)) |
|
|
10 |
18 |
|| (!(n % 11) && (n % 121)) |
|
40
|
22 |
266 |
|| (!(n % 13) && (n % 169)) ) return 0; |
|
|
14 |
8 |
|| (!(n % 13) && (n % 169)) ) return 0; |
|
41
|
123 |
173 |
} else if (k == 3) { |
|
42
|
39 |
84 |
if ( (!(n % 3) && (n % 27)) |
|
|
33 |
6 |
if ( (!(n % 3) && (n % 27)) |
|
43
|
23 |
94 |
|| (!(n % 5) && (n % 125)) |
|
|
20 |
3 |
|| (!(n % 5) && (n % 125)) |
|
44
|
59 |
55 |
|| (!(n % 7) && (n % 343)) |
|
|
57 |
2 |
|| (!(n % 7) && (n % 343)) |
|
45
|
10 |
102 |
|| (!(n % 11) && (n % 1331)) ) return 0; |
|
|
2 |
8 |
|| (!(n % 11) && (n % 1331)) ) return 0; |
|
47
|
54 |
119 |
if ( (!(n % 3) && (n % 81)) |
|
|
0 |
54 |
if ( (!(n % 3) && (n % 81)) |
|
48
|
18 |
101 |
|| (!(n % 5) && (n % 625)) |
|
|
0 |
18 |
|| (!(n % 5) && (n % 625)) |
|
49
|
18 |
83 |
|| (!(n % 7) && (n % 2401)) |
|
|
0 |
18 |
|| (!(n % 7) && (n % 2401)) |
|
50
|
10 |
73 |
|| (!(n % 11) && (n % 14641)) ) return 0; |
|
|
10 |
0 |
|| (!(n % 11) && (n % 14641)) ) return 0; |
|
76
|
457 |
0 |
if (n == 1 || powerof(n) >= k) return 1; |
|
|
137 |
320 |
if (n == 1 || powerof(n) >= k) return 1; |
|
91
|
134 |
186 |
CHECK_POWERFUL(n, 3, k); if (k >= 14 || n < ipow( 5,2*k)) return 0; |
|
|
38 |
148 |
CHECK_POWERFUL(n, 3, k); if (k >= 14 || n < ipow( 5,2*k)) return 0; |
|
|
0 |
38 |
CHECK_POWERFUL(n, 3, k); if (k >= 14 || n < ipow( 5,2*k)) return 0; |
|
|
30 |
38 |
CHECK_POWERFUL(n, 3, k); if (k >= 14 || n < ipow( 5,2*k)) return 0; |
|
|
38 |
0 |
CHECK_POWERFUL(n, 3, k); if (k >= 14 || n < ipow( 5,2*k)) return 0; |
|
|
0 |
38 |
CHECK_POWERFUL(n, 3, k); if (k >= 14 || n < ipow( 5,2*k)) return 0; |
|
|
134 |
186 |
CHECK_POWERFUL(n, 3, k); if (k >= 14 || n < ipow( 5,2*k)) return 0; |
|
|
186 |
0 |
CHECK_POWERFUL(n, 3, k); if (k >= 14 || n < ipow( 5,2*k)) return 0; |
|
|
108 |
78 |
CHECK_POWERFUL(n, 3, k); if (k >= 14 || n < ipow( 5,2*k)) return 0; |
|
92
|
0 |
78 |
CHECK_POWERFUL(n, 5, k); if (k >= 12 || n < ipow( 7,2*k)) return 0; |
|
|
20 |
58 |
CHECK_POWERFUL(n, 5, k); if (k >= 12 || n < ipow( 7,2*k)) return 0; |
|
|
0 |
20 |
CHECK_POWERFUL(n, 5, k); if (k >= 12 || n < ipow( 7,2*k)) return 0; |
|
|
10 |
20 |
CHECK_POWERFUL(n, 5, k); if (k >= 12 || n < ipow( 7,2*k)) return 0; |
|
|
20 |
0 |
CHECK_POWERFUL(n, 5, k); if (k >= 12 || n < ipow( 7,2*k)) return 0; |
|
|
0 |
20 |
CHECK_POWERFUL(n, 5, k); if (k >= 12 || n < ipow( 7,2*k)) return 0; |
|
|
0 |
78 |
CHECK_POWERFUL(n, 5, k); if (k >= 12 || n < ipow( 7,2*k)) return 0; |
|
|
78 |
0 |
CHECK_POWERFUL(n, 5, k); if (k >= 12 || n < ipow( 7,2*k)) return 0; |
|
|
21 |
57 |
CHECK_POWERFUL(n, 5, k); if (k >= 12 || n < ipow( 7,2*k)) return 0; |
|
93
|
0 |
57 |
CHECK_POWERFUL(n, 7, k); if (k >= 10 || n < ipow(11,2*k)) return 0; |
|
|
14 |
43 |
CHECK_POWERFUL(n, 7, k); if (k >= 10 || n < ipow(11,2*k)) return 0; |
|
|
0 |
14 |
CHECK_POWERFUL(n, 7, k); if (k >= 10 || n < ipow(11,2*k)) return 0; |
|
|
5 |
14 |
CHECK_POWERFUL(n, 7, k); if (k >= 10 || n < ipow(11,2*k)) return 0; |
|
|
14 |
0 |
CHECK_POWERFUL(n, 7, k); if (k >= 10 || n < ipow(11,2*k)) return 0; |
|
|
0 |
14 |
CHECK_POWERFUL(n, 7, k); if (k >= 10 || n < ipow(11,2*k)) return 0; |
|
|
0 |
57 |
CHECK_POWERFUL(n, 7, k); if (k >= 10 || n < ipow(11,2*k)) return 0; |
|
|
57 |
0 |
CHECK_POWERFUL(n, 7, k); if (k >= 10 || n < ipow(11,2*k)) return 0; |
|
|
16 |
41 |
CHECK_POWERFUL(n, 7, k); if (k >= 10 || n < ipow(11,2*k)) return 0; |
|
95
|
41 |
0 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
|
0 |
41 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
|
0 |
150 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
|
0 |
150 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
|
0 |
150 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
|
37 |
113 |
START_DO_FOR_EACH_PRIME(11, rootint(n,2*k)) { |
|
96
|
4 |
109 |
LCHECK_POWERFUL(n, p, k); |
|
|
11 |
98 |
LCHECK_POWERFUL(n, p, k); |
|
|
0 |
11 |
LCHECK_POWERFUL(n, p, k); |
|
|
0 |
11 |
LCHECK_POWERFUL(n, p, k); |
|
|
11 |
0 |
LCHECK_POWERFUL(n, p, k); |
|
|
0 |
11 |
LCHECK_POWERFUL(n, p, k); |
|
105
|
0 |
15370 |
if (r <= k) return lim; |
|
107
|
5502 |
9868 |
if (r-1 == k) { |
|
108
|
15934 |
5502 |
for (i = 1; i <= lim; i++) |
|
109
|
12969 |
2965 |
if (isf[i] && gcd_ui(m,i) == 1) |
|
|
10143 |
2826 |
if (isf[i] && gcd_ui(m,i) == 1) |
|
112
|
19329 |
9868 |
for (i = 1; i <= lim; i++) |
|
113
|
17162 |
2167 |
if (isf[i] && gcd_ui(m,i) == 1) |
|
|
14970 |
2192 |
if (isf[i] && gcd_ui(m,i) == 1) |
|
123
|
239 |
54 |
if (k <= 1 || n <= 1) return n; |
|
|
7 |
232 |
if (k <= 1 || n <= 1) return n; |
|
124
|
0 |
232 |
if (k >= BITS_PER_WORD) return 1; |
|
129
|
54 |
178 |
if (k == 2) { |
|
130
|
86837 |
54 |
for (i = 1; i <= lim; i++) |
|
131
|
52851 |
33986 |
if (isf[i]) |
|
137
|
490 |
178 |
for (i = 1; i <= lim; i++) |
|
138
|
400 |
90 |
if (isf[i]) |
|
164
|
3 |
0 |
if (k == 0 || k >= BITS_PER_WORD) return 0; |
|
|
0 |
3 |
if (k == 0 || k >= BITS_PER_WORD) return 0; |
|
165
|
3 |
0 |
if (k == 1 || n <= 1) return n; |
|
|
0 |
3 |
if (k == 1 || n <= 1) return n; |
|
167
|
2 |
1 |
max = (k <= 10) ? maxpow[k] : powerful_count(UV_MAX,k); |
|
168
|
0 |
3 |
if (n > max) return 0; |
|
170
|
1 |
2 |
if (n <= 20 && k >= mink[n]) return UVCONST(1) << (k+(n-2)); |
|
|
0 |
1 |
if (n <= 20 && k >= mink[n]) return UVCONST(1) << (k+(n-2)); |
|
175
|
1 |
2 |
if (k == 2) { /* From Mincu and Panaitopol 2009 */ |
|
180
|
0 |
1 |
hi = (n < 170) ? 8575 : (dhi >= UV_MAX) ? UV_MAX : 1 + (UV) dhi; |
|
|
0 |
0 |
hi = (n < 170) ? 8575 : (dhi >= UV_MAX) ? UV_MAX : 1 + (UV) dhi; |
|
181
|
0 |
2 |
} else if (k == 3) { |
|
183
|
0 |
0 |
if (n < 84000) { |
|
193
|
0 |
0 |
if (n < 900) dhi *= 1.3; |
|
194
|
0 |
0 |
if (n < 160) dhi = 1.3 * dhi + 600; |
|
195
|
0 |
0 |
hi = (dhi >= UV_MAX) ? UV_MAX : 1 + (UV) dhi; |
|
196
|
1 |
1 |
} else if (k <= 10) { |
|
198
|
1 |
0 |
if (n < 200) { |
|
210
|
0 |
1 |
hi = (dhi >= UV_MAX) ? UV_MAX : 1 + (UV) dhi; |
|
215
|
1 |
0 |
if (n < max) hi = lo + (((double)n / (double)max) * (UV_MAX-lo) + 1); |
|
226
|
0 |
21879 |
if (r < k) return m; |
|
230
|
10182 |
11697 |
if (r == k) return m * powersum(rootdiv, r); |
|
232
|
31504 |
11697 |
for (sum = 0, i = 1; i <= rootdiv; i++) |
|
233
|
25543 |
5961 |
if (isf[i] && gcd_ui(i,m) == 1) |
|
|
21706 |
3837 |
if (isf[i] && gcd_ui(i,m) == 1) |
|
260
|
178 |
1 |
if (k == 0 || n == 0) return 0; |
|
|
0 |
178 |
if (k == 0 || n == 0) return 0; |
|
261
|
0 |
178 |
if (k >= 64) return 1; |
|
262
|
178 |
0 |
if (k < 41 && n > maxpow[k]) return 0; |
|
|
3 |
175 |
if (k < 41 && n > maxpow[k]) return 0; |
|
271
|
2 |
173 |
if (k == 1) return (n+1)/2 * (n|1); |
|
283
|
219 |
391 |
if (r > k) { |
|
284
|
979 |
219 |
for (v = beg; v <= end; v++) { |
|
285
|
735 |
244 |
if (gcd_ui(m,v) == 1 && is_square_free(v)) |
|
|
602 |
133 |
if (gcd_ui(m,v) == 1 && is_square_free(v)) |
|
289
|
370 |
21 |
if (lo > m) { |
|
292
|
365 |
5 |
if (ipow(beg,r) != lom) beg++; |
|
294
|
77 |
391 |
for (v = beg; v <= end; v++) |
|
306
|
1 |
9 |
: (lo < 400000000U) ? 160 : 600 ) |
|
|
0 |
1 |
: (lo < 400000000U) ? 160 : 600 ) |
|
307
|
5 |
5 |
* ((k <= 2) ? 1 : 4); |
|
310
|
1 |
9 |
if (lo < 1) lo = 1; |
|
312
|
0 |
10 |
if (hi < lo) { |
|
315
|
2 |
8 |
} else if (k <= 1) { |
|
317
|
0 |
2 |
New(0, pn, npn, UV); |
|
318
|
24 |
2 |
for (i = lo; i <= hi; i++) |
|
320
|
8 |
0 |
} else if ((lo+single_thresh) > hi || lo > (UV_MAX-single_thresh)) { |
|
|
0 |
8 |
} else if ((lo+single_thresh) > hi || lo > (UV_MAX-single_thresh)) { |
|
321
|
0 |
0 |
New(0, pn, hi-lo+1, UV); |
|
322
|
0 |
0 |
for (i = lo, npn = 0; i <= hi && i != 0; i++) |
|
|
0 |
0 |
for (i = lo, npn = 0; i <= hi && i != 0; i++) |
|
323
|
0 |
0 |
if (is_powerful(i,k)) |
|
326
|
4 |
4 |
npn = powerful_count(hi,k) - ((lo <= 1) ? 0 : powerful_count(lo-1,k)); |
|
327
|
0 |
8 |
New(0, pn, npn, UV); |
|
330
|
0 |
8 |
MPUassert(i == npn, "Number of powerful numbers generated != count"); |