| line |
true |
false |
branch |
|
20
|
1269 |
684 |
for (i = 0; i < nfacs; i++) { |
|
22
|
295 |
974 |
if (f == lastf) { totient *= f; } |
|
56
|
78 |
0 |
if (hi < lo || count == 0 || count > (Size_t)((SSize_t)-1)) |
|
|
0 |
78 |
if (hi < lo || count == 0 || count > (Size_t)((SSize_t)-1)) |
|
59
|
67 |
11 |
if (hi < 16) { |
|
61
|
0 |
67 |
New(0, totients, count, UV); |
|
62
|
249 |
67 |
for (i = 0; i < count; i++) |
|
67
|
6 |
5 |
if (lo > 0) { /* With a non-zero start, use our ranged factoring */ |
|
71
|
0 |
6 |
New(0, totients, count, UV); |
|
72
|
40 |
6 |
for (i = 0; i < count; i++) { |
|
84
|
0 |
5 |
if (hi == UV_MAX) |
|
88
|
0 |
5 |
New(0, prime, max_nprimes(sqrthi), uint32_t); |
|
89
|
0 |
5 |
Newz(0, totients, count, UV); |
|
92
|
2063 |
5 |
for (i = 1; i <= hi/2; i += 2) { |
|
94
|
612 |
1451 |
if (toti == 0) { |
|
96
|
38 |
574 |
if (i <= sqrthi) |
|
99
|
4400 |
9 |
for (j = 0; j < nprimes; j++) { |
|
101
|
1390 |
3010 |
if (index > hi) break; |
|
102
|
664 |
2346 |
if (i % prime[j] == 0) { |
|
110
|
2062 |
1 |
if (i+1 <= hi/2) |
|
116
|
2064 |
5 |
for (; i <= hi; i += 2) |
|
117
|
500 |
1564 |
if (totients[i] == 0) |
|
151
|
0 |
62 |
if (n <= 2) return n; |
|
152
|
0 |
62 |
if (n > MAX_TOTSUM) return 0; |
|
160
|
111 |
62 |
for (sum = 1, i = 2; i <= sqrtn; i++) { |
|
164
|
32 |
30 |
if (flag) sumcache2[sqrtn] = sumcache1[sqrtn]; |
|
166
|
141 |
62 |
for (i = sqrtn - flag; i > 0; i--) { |
|
172
|
151 |
141 |
for (k = 2, j = k*i; j <= sqrtn; k++) { |
|
177
|
113 |
141 |
for (; k <= s; k++) { |
|
181
|
75 |
66 |
if (m < (UV)s * ((UV)s+1)) |
|
208
|
0 |
378 |
if (n < csize) return cdata[n]; |
|
211
|
437 |
0 |
for (hashk = 0; hashk <= probes; hashk++) { |
|
212
|
267 |
170 |
if (thash.nhash[hn] == n) return thash.shash[hn]; |
|
213
|
111 |
59 |
if (thash.nhash[hn] == 0) break; |
|
214
|
47 |
12 |
hn = (hn+1 < thash.hsize) ? hn+1 : 0; |
|
222
|
14734 |
111 |
for (k = 2; k <= lim; k++) { |
|
223
|
14358 |
376 |
sum -= _CACHED_SUMT(n/k); |
|
224
|
14734 |
0 |
sum -= ((n/k) - (n/(k+1))) * _CACHED_SUMT(k); |
|
226
|
51 |
60 |
if (s > lim) |
|
227
|
51 |
0 |
sum -= ((n/s) - (n/(s+1))) * _CACHED_SUMT(s); |
|
229
|
112 |
0 |
for (; hashk <= probes; hashk++) { |
|
230
|
111 |
1 |
if (thash.nhash[hn] == 0) { |
|
235
|
1 |
0 |
hn = (hn+1 < thash.hsize) ? hn+1 : 0; |
|
244
|
17 |
64 |
if (n <= 2) return n; |
|
245
|
0 |
64 |
if (n > MAX_TOTSUM) return 0; |
|
247
|
62 |
2 |
if (n < 4000) return _sumtotient_direct(n); |
|
253
|
7921 |
2 |
for (i = 2; i < csize; i++) |
|
257
|
0 |
2 |
Newz(0, thash.nhash, thash.hsize, UV); |
|
258
|
0 |
2 |
New( 0, thash.shash, thash.hsize, UV); |
|
284
|
0 |
0 |
if (n < csize) return cdata[n]; |
|
287
|
0 |
0 |
for (hashk = 0; hashk <= probes; hashk++) { |
|
288
|
0 |
0 |
if (thash.nhash[hn] == n) return thash.shash[hn]; |
|
289
|
0 |
0 |
if (thash.nhash[hn] == 0) break; |
|
290
|
0 |
0 |
hn = (hn+hinc < thash.hsize) ? hn+hinc : hn+hinc-thash.hsize; |
|
298
|
0 |
0 |
for (k = 2; k <= lim; k++) { |
|
299
|
0 |
0 |
sum -= _CACHED_SUMT128(n/k); |
|
300
|
0 |
0 |
sum -= ((n/k) - (n/(k+1))) * _CACHED_SUMT128(k); |
|
302
|
0 |
0 |
if (s > lim) |
|
303
|
0 |
0 |
sum -= ((n/s) - (n/(s+1))) * _CACHED_SUMT128(s); |
|
305
|
0 |
0 |
for (; hashk <= probes; hashk++) { |
|
306
|
0 |
0 |
if (thash.nhash[hn] == 0) { |
|
311
|
0 |
0 |
hn = (hn+hinc < thash.hsize) ? hn+hinc : hn+hinc-thash.hsize; |
|
322
|
0 |
0 |
if (n <= 2) { *hi_sum = 0; *lo_sum = n; return 1; } |
|
329
|
0 |
0 |
if (csize > 400000000U) { /* Limit to 3GB */ |
|
335
|
0 |
0 |
for (i = 2; i < csize; i++) |
|
340
|
0 |
0 |
Newz(0, thash.nhash, thash.hsize, UV); |
|
341
|
0 |
0 |
New( 0, thash.shash, thash.hsize, uint128_t); |
|
347
|
0 |
0 |
if (_XS_get_verbose() >= 2) { |
|
349
|
0 |
0 |
for (i = 0; i < thash.hsize; i++) |
|
381
|
490 |
0 |
if (k == 0 || n <= 1) return (n == 1); |
|
|
11 |
479 |
if (k == 0 || n <= 1) return (n == 1); |
|
382
|
457 |
22 |
if (k > 6 || (k > 1 && n >= jordan_overflow[k-2])) return 0; |
|
|
321 |
136 |
if (k > 6 || (k > 1 && n >= jordan_overflow[k-2])) return 0; |
|
|
0 |
321 |
if (k > 6 || (k > 1 && n >= jordan_overflow[k-2])) return 0; |
|
386
|
205 |
457 |
while ((n & 0x3) == 0) { n >>= 1; totient *= (1<
|
|
387
|
226 |
231 |
if ((n & 0x1) == 0) { n >>= 1; totient *= ((1<
|
|
390
|
503 |
457 |
for (i = 0; i < nf.nfactors; i++) { |
|
395
|
77 |
503 |
while (e-- > 1) |
|
409
|
215 |
247 |
if (n & 1) return 0; |
|
410
|
10 |
237 |
if ((n & (n-1)) == 0) return 1; |
|
412
|
0 |
237 |
if (n == 1) return 1; |
|
413
|
71 |
166 |
if (n < maxd && is_prime(2*n+1)) return 1; |
|
|
17 |
54 |
if (n < maxd && is_prime(2*n+1)) return 1; |
|
416
|
960 |
114 |
for (i = 0, res = 0; i < ndivisors && divs[i] < maxd && res == 0; i++) { |
|
|
867 |
93 |
for (i = 0, res = 0; i < ndivisors && divs[i] < maxd && res == 0; i++) { |
|
|
854 |
13 |
for (i = 0, res = 0; i < ndivisors && divs[i] < maxd && res == 0; i++) { |
|
418
|
508 |
346 |
if (!is_prime(p)) continue; |
|
421
|
398 |
2 |
if (r == p || _totpred(r, d)) { res = 1; break; } |
|
|
11 |
387 |
if (r == p || _totpred(r, d)) { res = 1; break; } |
|
422
|
333 |
54 |
if (r % p) break; |
|
431
|
124 |
1 |
return (n == 0 || (n & 1)) ? (n==1) : _totpred(n,n); |
|
|
60 |
64 |
return (n == 0 || (n & 1)) ? (n==1) : _totpred(n,n); |
|
443
|
1 |
103 |
if (n == 1) return 2; |
|
444
|
102 |
1 |
if (n < 1 || n & 1) return 0; |
|
|
49 |
53 |
if (n < 1 || n & 1) return 0; |
|
445
|
15 |
38 |
if (is_prime(n >> 1)) { /* Coleman Remark 3.3 (Thm 3.1) and Prop 6.2 */ |
|
446
|
8 |
7 |
if (!is_prime(n+1)) return 0; |
|
447
|
5 |
2 |
if (n >= 10) return 2; |
|
456
|
2191 |
40 |
for (i = 0; i < ndivisors; i++) { |
|
458
|
734 |
1457 |
if (is_prime(p)) { |
|
461
|
887 |
734 |
for (j = 0; j <= v; j++) { |
|
463
|
40 |
847 |
if (np == 1) { |
|
467
|
467221 |
0 |
for (k = 0; k < ndivisors && divs[k] <= ndiv; k++) { |
|
|
466374 |
847 |
for (k = 0; k < ndivisors && divs[k] <= ndiv; k++) { |
|
469
|
382237 |
84137 |
if ((ndiv % d2) != 0) continue; |
|
471
|
40356 |
43781 |
if (val > 0) { |
|
495
|
1 |
9 |
if (n == 1) { |
|
501
|
8 |
1 |
if (n < 1 || n & 1) { |
|
|
1 |
7 |
if (n < 1 || n & 1) { |
|
505
|
3 |
4 |
if (is_prime(n >> 1)) { /* Coleman Remark 3.3 (Thm 3.1) and Prop 6.2 */ |
|
506
|
1 |
2 |
if (!is_prime(n+1)) { |
|
509
|
0 |
2 |
} else if (n >= UV_MAX/2) { /* overflow */ |
|
512
|
1 |
1 |
} else if (n >= 10) { |
|
525
|
0 |
5 |
if (n >= (BITS_PER_WORD == 64 ? UVCONST(2459565884898017280) : 716636160UL)) { |
|
535
|
102 |
5 |
for (i = 0; i < ndivisors; i++) { |
|
537
|
37 |
65 |
if (is_prime(p)) { |
|
540
|
58 |
37 |
for (j = 0; j <= v; j++) { |
|
542
|
1283 |
5 |
for (k = 0; k < ndivisors && divs[k] <= ndiv; k++) { |
|
|
1230 |
53 |
for (k = 0; k < ndivisors && divs[k] <= ndiv; k++) { |
|
544
|
550 |
680 |
if ((ndiv % d2) != 0) continue; |
|
546
|
264 |
416 |
if (d == 1 && d2*dp != n) continue; |
|
|
246 |
18 |
if (d == 1 && d2*dp != n) continue; |
|
548
|
136 |
298 |
if (vals != 0) |
|
561
|
5 |
0 |
if (tlist != 0 && *ntotients > 0) { |
|
|
5 |
0 |
if (tlist != 0 && *ntotients > 0) { |
|
562
|
0 |
5 |
New(0, totlist, *ntotients, UV); |