| line |
true |
false |
branch |
|
119
|
0 |
3 |
if (a < 4) { |
|
120
|
0 |
0 |
return (a==0) ? x : |
|
121
|
0 |
0 |
(a==1) ? x-x/2 : |
|
123
|
0 |
0 |
: (x/30U) * 8U + _s3[x % 30U]; |
|
125
|
0 |
3 |
MPUassert(a <= PHIS, "phi_small: a too large"); |
|
126
|
0 |
3 |
if (x < _snth[a+1]) return (x>0); |
|
128
|
10 |
3 |
for (npos = nneg = 0, xpos[npos++] = x; a > 4U; a--) { |
|
130
|
16 |
10 |
for (i = 0; i < opos; i++) |
|
131
|
15 |
1 |
if (xpos[i] >= _snth[a]) |
|
133
|
13 |
10 |
for (i = 0; i < oneg; i++) |
|
134
|
12 |
1 |
if (xneg[i] >= _snth[a]) |
|
137
|
15 |
3 |
for (i = 0; i < npos; i++) |
|
139
|
15 |
3 |
for (i = 0; i < nneg; i++) |
|
151
|
0 |
0 |
if (x < 1 || a >= x) return (x > 0); |
|
|
0 |
0 |
if (x < 1 || a >= x) return (x > 0); |
|
152
|
0 |
0 |
if (a <= PHIS || x <= PHIS_XMIN) return phi_small(x, a); |
|
|
0 |
0 |
if (a <= PHIS || x <= PHIS_XMIN) return phi_small(x, a); |
|
154
|
0 |
0 |
npa = (a <= 25) ? _snth[a] : nth_prime(a); |
|
157
|
0 |
0 |
for (i = PHIS+1; i <= a; i++) { |
|
159
|
0 |
0 |
xp = FAST_DIV(x,p); |
|
160
|
0 |
0 |
if (xp < p) { |
|
161
|
0 |
0 |
while (x < npa) { |
|
189
|
2560 |
5 |
for (a = 0; a < PHICACHEA; a++) { |
|
193
|
0 |
5 |
cache->xlim = (xlim < 0xFFFFFFFFU) ? xlim : xlim-1; /* Reserve 0xFFFFFFFF */ |
|
199
|
2560 |
5 |
for (a = 0; a < PHICACHEA; a++) { |
|
200
|
41 |
2519 |
if (cache->val[a] != 0) |
|
208
|
1183 |
1304 |
if (sum < 0) sum = -sum; |
|
209
|
0 |
2487 |
if (sum > 65535) return; /* If sum is too large for the cache, ignore it. */ |
|
210
|
45 |
2442 |
if (x >= cache->siz[a]) { |
|
212
|
41 |
4 |
if (cache->val[a] == 0) { |
|
216
|
883 |
4 |
for (i = cache->siz[a]; i < newsize; i++) /* Zero the new entries */ |
|
239
|
1 |
4 |
if (xlim < 256) xlim = 256; |
|
270
|
1736 |
10930 |
if (x < primes[a+1]) |
|
272
|
142 |
10788 |
else if (a <= PHIC) |
|
274
|
8142 |
2646 |
else if (PHI_IS_X_SMALL(x,a)) |
|
|
2366 |
5776 |
else if (PHI_IS_X_SMALL(x,a)) |
|
278
|
7911 |
511 |
mapx = (a < PHICACHEA) ? _toindex210(x) : 0; |
|
280
|
7911 |
511 |
if (a < PHICACHEA && mapx < pcache->siz[a]) { |
|
|
4408 |
3503 |
if (a < PHICACHEA && mapx < pcache->siz[a]) { |
|
282
|
1966 |
2442 |
if (v != 0) |
|
286
|
910 |
5546 |
UV xp, i, iters = ((UV)a*a > x) ? PHI_PRIMECOUNT(isqrt(x)) : a; |
|
292
|
6456 |
0 |
if (c < iters) |
|
293
|
6456 |
0 |
sum += -sign * tablephi(FAST_DIV(x,primes[c+1]), c); |
|
294
|
12251 |
1751 |
for (i = c+1; i < iters; i++) { |
|
295
|
12251 |
0 |
xp = FAST_DIV(x,primes[i+1]); |
|
296
|
9974 |
2277 |
if (PHI_IS_X_SMALL(xp,i)) |
|
|
4705 |
5269 |
if (PHI_IS_X_SMALL(xp,i)) |
|
300
|
44441 |
6282 |
for (; i < iters; i++) { |
|
301
|
44441 |
0 |
xp = FAST_DIV(x,primes[i+1]); |
|
302
|
174 |
44267 |
if (xp < primes[i+1]) |
|
306
|
174 |
6282 |
if (i < iters) |
|
309
|
5945 |
511 |
if (a < PHICACHEA && mapx <= pcache->xlim) |
|
|
2487 |
3458 |
if (a < PHICACHEA && mapx <= pcache->xlim) |
|
321
|
4 |
0 |
if (x < 1 || a >= x) return (x > 0); |
|
|
0 |
4 |
if (x < 1 || a >= x) return (x > 0); |
|
322
|
4 |
0 |
if (a <= PHIS || x <= PHIS_XMIN) return phi_small(x, a); |
|
|
0 |
4 |
if (a <= PHIS || x <= PHIS_XMIN) return phi_small(x, a); |
|
323
|
0 |
4 |
if (a > 203280221) croak("64-bit phi out of range"); |
|
326
|
4 |
0 |
if (isqrt(x) > primes_to_n) primes_to_n = isqrt(x); |
|
329
|
4 |
0 |
if (primes[a] < x) { |
|
373
|
0 |
0 |
if (l->a != 0) { |
|
374
|
0 |
0 |
if (verbose > 2) printf("FREE list %p\n", l->a); |
|
387
|
0 |
0 |
if (n > 0 && arr[n-1].v <= val) { |
|
|
0 |
0 |
if (n > 0 && arr[n-1].v <= val) { |
|
388
|
0 |
0 |
if (arr[n-1].v == val) { |
|
394
|
0 |
0 |
if (n >= l->size) { |
|
396
|
0 |
0 |
if (l->size == 0) { |
|
398
|
0 |
0 |
if (verbose>2) printf("ALLOCing list, size %lu (%luk)\n", new_size, new_size*sizeof(vc_t)/1024); |
|
399
|
0 |
0 |
New(0, l->a, new_size, vc_t); |
|
402
|
0 |
0 |
if (verbose>2) printf("REALLOCing list %p, new size %lu (%luk)\n",l->a,new_size, new_size*sizeof(vc_t)/1024); |
|
403
|
0 |
0 |
Renew( l->a, new_size, vc_t ); |
|
426
|
0 |
0 |
for (ai = 0, bi = 0, bj = 0; bi < bn; bi++) { |
|
429
|
0 |
0 |
while (ai+8 < an && aa[ai+8].v > bval) ai += 8; |
|
|
0 |
0 |
while (ai+8 < an && aa[ai+8].v > bval) ai += 8; |
|
430
|
0 |
0 |
while (ai < an && aa[ai ].v > bval) ai++; |
|
|
0 |
0 |
while (ai < an && aa[ai ].v > bval) ai++; |
|
432
|
0 |
0 |
if (ai >= an) { |
|
433
|
0 |
0 |
if (bi == bj) |
|
436
|
0 |
0 |
while (bi < bn) |
|
440
|
0 |
0 |
if (aa[ai].v == bval) |
|
445
|
0 |
0 |
if (verbose>3) printf(" removed %lu duplicates from b\n", bn - bj); |
|
448
|
0 |
0 |
if (bn == 0) { /* In case they were all duplicates */ |
|
455
|
0 |
0 |
if ((long)a->size < kn) { /* Make A big enough to hold kn elements */ |
|
457
|
0 |
0 |
if (verbose>2) printf("REALLOCing list %p, new size %lu (%luk)\n", a->a, new_size, new_size*sizeof(vc_t)/1024); |
|
458
|
0 |
0 |
Renew( a->a, new_size, vc_t ); |
|
466
|
0 |
0 |
for (k = kn-1; k >= 0 && bi >= 0; k--) { |
|
|
0 |
0 |
for (k = kn-1; k >= 0 && bi >= 0; k--) { |
|
469
|
0 |
0 |
while (ai >= 15 && aa[ai-15].v < bval) ai -= 16; |
|
|
0 |
0 |
while (ai >= 15 && aa[ai-15].v < bval) ai -= 16; |
|
470
|
0 |
0 |
while (ai >= 3 && aa[ai- 3].v < bval) ai -= 4; |
|
|
0 |
0 |
while (ai >= 3 && aa[ai- 3].v < bval) ai -= 4; |
|
471
|
0 |
0 |
while (ai >= 0 && aa[ai ].v < bval) ai--; |
|
|
0 |
0 |
while (ai >= 0 && aa[ai ].v < bval) ai--; |
|
472
|
0 |
0 |
if (startai > ai) { |
|
476
|
0 |
0 |
if (ai >= 0 && aa[ai].v == bval) croak("deduplication error"); |
|
|
0 |
0 |
if (ai >= 0 && aa[ai].v == bval) croak("deduplication error"); |
|
491
|
0 |
0 |
while (aj < an) { |
|
492
|
0 |
0 |
if (aa[aj].c != 0) { |
|
493
|
0 |
0 |
if (ai != aj) |
|
513
|
0 |
0 |
if (x < 1 || a >= x) return (x > 0); |
|
|
0 |
0 |
if (x < 1 || a >= x) return (x > 0); |
|
514
|
0 |
0 |
if (x <= PHIC || a <= PHIC) return tablephi(x, (a > PHIC) ? PHIC : a); |
|
|
0 |
0 |
if (x <= PHIC || a <= PHIC) return tablephi(x, (a > PHIC) ? PHIC : a); |
|
515
|
0 |
0 |
if (a > 203280221) croak("64-bit phi out of range"); |
|
518
|
0 |
0 |
if (isqrt(x) > primes_to_n) primes_to_n = isqrt(x); |
|
522
|
0 |
0 |
if (x < lastprime) { Safefree(primes); return 1; } |
|
530
|
0 |
0 |
while (a > PHIC) { |
|
534
|
0 |
0 |
for (i = 0; i < a1.n; i++) { |
|
535
|
0 |
0 |
sval = FAST_DIV(arr[i].v, primea); |
|
537
|
0 |
0 |
if (sval < primea || PHI_IS_X_SMALL(sval, a-1)) |
|
|
0 |
0 |
if (sval < primea || PHI_IS_X_SMALL(sval, a-1)) |
|
|
0 |
0 |
if (sval < primea || PHI_IS_X_SMALL(sval, a-1)) |
|
541
|
0 |
0 |
for ( ; i < a1.n; i++) { |
|
542
|
0 |
0 |
sval = FAST_DIV(arr[i].v, primea); |
|
543
|
0 |
0 |
if (sval < primea) |
|
547
|
0 |
0 |
for ( ; i < a1.n; i++) |
|
554
|
0 |
0 |
if ( a1.n > NTHRESH ) { |
|
556
|
0 |
0 |
if (verbose > 0) printf("clipping small values at a=%lu a1.n=%lu \n", a, a1.n); |
|
557
|
0 |
0 |
for (i = 0; i < a1.n-NTHRESH+NTHRESH/50; i++) { |
|
560
|
0 |
0 |
if (count != 0) { |
|
574
|
0 |
0 |
for (i = 0; i < a1.n; i++) |
|
587
|
379060 |
0 |
: (a <= PHIS) ? phi_small(n, a) |
|
588
|
0 |
0 |
: phi_recurse_small(n, a); |
|
594
|
0 |
0 |
return (a <= PHIS) ? phi_small(n, a) : phi_recurse(n, a); |
|
604
|
0 |
1 |
if (a > 203280221) a = 203280221; |
|
606
|
1 |
0 |
if (npa < isqrt(x)) npa = isqrt(x); |
|
614
|
2626 |
0 |
if (x < 1 || a >= x) return (x > 0); |
|
|
0 |
2626 |
if (x < 1 || a >= x) return (x > 0); |
|
615
|
2626 |
0 |
if (x <= PHIC || a <= PHIC) return tablephi(x, (a > PHIC) ? PHIC : a); |
|
|
70 |
2556 |
if (x <= PHIC || a <= PHIC) return tablephi(x, (a > PHIC) ? PHIC : a); |
|
616
|
0 |
2556 |
if (a > (x >> 1)) return 1; |
|
619
|
0 |
2556 |
if (a > 203280221) { /* prime_count(2**32) */ |
|
621
|
0 |
0 |
return (a >= pc) ? 1 : pc - a + 1; |
|
623
|
0 |
2556 |
if (a > d->lastidx) |
|
649
|
21 |
1 |
if (x < 1 || a >= x) return (x > 0); |
|
|
1 |
20 |
if (x < 1 || a >= x) return (x > 0); |
|
650
|
20 |
0 |
if (x <= PHIC || a <= PHIC) return tablephi(x, (a > PHIC) ? PHIC : a); |
|
|
11 |
9 |
if (x <= PHIC || a <= PHIC) return tablephi(x, (a > PHIC) ? PHIC : a); |
|
653
|
0 |
9 |
if (a > (x >> 1)) |
|
655
|
8 |
1 |
if (a >= sqrtx || a > 203280221) { /* 203280221 = prime_count(2^32) */ |
|
|
0 |
8 |
if (a >= sqrtx || a > 203280221) { /* 203280221 = prime_count(2^32) */ |
|
657
|
1 |
0 |
return (a >= pc) ? 1 : pc - a + 1; |
|
662
|
3 |
5 |
if (a <= PHIS) return phi_small(x, a); |
|
663
|
0 |
5 |
if (a <= PHIR) return phi_recurse_small(x, a); |
|
666
|
0 |
5 |
if (prime_count_upper(x) <= a) |
|
669
|
1 |
4 |
if (prime_count_upper(sqrtx) < a) { |
|
671
|
1 |
0 |
return (a >= pc) ? 1 : pc - a + 1; |
|
678
|
4 |
0 |
if (x < 1e10) |
|
681
|
0 |
0 |
if ( (x >= 1e10 && x < 1e11 && a < 2000) || |
|
|
0 |
0 |
if ( (x >= 1e10 && x < 1e11 && a < 2000) || |
|
|
0 |
0 |
if ( (x >= 1e10 && x < 1e11 && a < 2000) || |
|
682
|
0 |
0 |
(x >= 1e11 && x < 1e12 && a < 4000) || |
|
|
0 |
0 |
(x >= 1e11 && x < 1e12 && a < 4000) || |
|
|
0 |
0 |
(x >= 1e11 && x < 1e12 && a < 4000) || |
|
683
|
0 |
0 |
(x >= 1e12 && x < 1e13 && a < 10000) || |
|
|
0 |
0 |
(x >= 1e12 && x < 1e13 && a < 10000) || |
|
|
0 |
0 |
(x >= 1e12 && x < 1e13 && a < 10000) || |
|
684
|
0 |
0 |
(x >= 1e13 && x < 1e14 && a < 24000) || |
|
|
0 |
0 |
(x >= 1e13 && x < 1e14 && a < 24000) || |
|
|
0 |
0 |
(x >= 1e13 && x < 1e14 && a < 24000) || |
|
685
|
0 |
0 |
(x >= 1e14 && x < 1e15 && a < 80000) || |
|
|
0 |
0 |
(x >= 1e14 && x < 1e15 && a < 80000) || |
|
|
0 |
0 |
(x >= 1e14 && x < 1e15 && a < 80000) || |
|
686
|
0 |
0 |
(x > 1e15 && a < 150000) ) |
|
|
0 |
0 |
(x > 1e15 && a < 150000) ) |