| line |
true |
false |
branch |
|
46
|
116227 |
0 |
MPUassert(n >= primes[0] && n < primes[lastidx], "prime count via binary search out of range"); |
|
|
0 |
116227 |
MPUassert(n >= primes[0] && n < primes[lastidx], "prime count via binary search out of range"); |
|
47
|
2364951 |
116227 |
while (i < j) { |
|
49
|
853412 |
1511539 |
if (primes[mid] <= n) i = mid+1; |
|
61
|
14 |
2453 |
if (n > 1000000) { /* Upfront work to speed up the many small calls */ |
|
63
|
3 |
11 |
if (nprecalc > _MPU_LMO_CROSSOVER) nprecalc = _MPU_LMO_CROSSOVER; |
|
69
|
2467 |
0 |
if (sqrtn >= 2) sum += prime_count(n/2) - pc++; |
|
70
|
2467 |
0 |
if (sqrtn >= 3) sum += prime_count(n/3) - pc++; |
|
71
|
2466 |
1 |
if (sqrtn >= 5) sum += prime_count(n/5) - pc++; |
|
72
|
2466 |
1 |
if (sqrtn >= 7) { |
|
76
|
2466 |
2466 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
77
|
160576 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
2466 |
158110 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
158110 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
160576 |
5389 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
7855 |
2466 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
79
|
116227 |
41883 |
if (np < xlim) { |
|
80
|
116213 |
14 |
if (xarr == 0 || np < xbeg) { |
|
|
0 |
116213 |
if (xarr == 0 || np < xbeg) { |
|
81
|
0 |
14 |
if (xarr != 0) { Safefree(xarr); xarr = 0; } |
|
84
|
0 |
14 |
if (xend - xbeg > xmax) xbeg = xend - xmax; |
|
98
|
14 |
2452 |
if (xarr != 0) { Safefree(xarr); xarr = 0; } |
|
151
|
0 |
31 |
if (lo < 4) lo = 4; |
|
152
|
0 |
31 |
if (hi > MPU_MAX_SEMI_PRIME) hi = MPU_MAX_SEMI_PRIME; |
|
154
|
17 |
14 |
if (hi <= _semiprimelist[NSEMIPRIMELIST-1]) { |
|
155
|
1 |
16 |
if (semis == 0) { |
|
156
|
11 |
0 |
for (i = 1; i < NSEMIPRIMELIST && _semiprimelist[i] <= hi; i++) |
|
|
10 |
1 |
for (i = 1; i < NSEMIPRIMELIST && _semiprimelist[i] <= hi; i++) |
|
157
|
6 |
4 |
if (_semiprimelist[i] >= lo) |
|
161
|
154 |
0 |
for (i = 1; i < NSEMIPRIMELIST && _semiprimelist[i] <= hi; i++) |
|
|
138 |
16 |
for (i = 1; i < NSEMIPRIMELIST && _semiprimelist[i] <= hi; i++) |
|
162
|
88 |
50 |
if (_semiprimelist[i] >= lo) |
|
170
|
14 |
0 |
if (sqrtn*sqrtn < hi && sqrtn < (UVCONST(1)<<(BITS_PER_WORD/2))-1) sqrtn++; |
|
|
14 |
0 |
if (sqrtn*sqrtn < hi && sqrtn < (UVCONST(1)<<(BITS_PER_WORD/2))-1) sqrtn++; |
|
172
|
14 |
0 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
14 |
0 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
42 |
27452 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
28 |
14 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
14 |
14 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
8247 |
19205 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
1 |
8275 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
29 |
8246 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
1 |
8246 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
0 |
27451 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
13 |
27480 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
173
|
27457 |
23 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
423363 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
395883 |
27480 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
2862 |
24618 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
97572 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
70092 |
27480 |
MARKSEMI(p,nfacs,lo,hi); |
|
175
|
6 |
8 |
if (cutn < sqrtn) { |
|
179
|
6 |
6 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
180
|
79407 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
6 |
79401 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
79401 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
79407 |
3879 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
3885 |
6 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
181
|
79399 |
2 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
95809 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
16408 |
79401 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
25968 |
53433 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
79401 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
0 |
79401 |
MARKSEMI(p,nfacs,lo,hi); |
|
186
|
3 |
11 |
if (semis == 0) { |
|
187
|
44690 |
3 |
for (i = lo; i <= hi; i++) |
|
188
|
7394 |
37296 |
if (nfacs[i-lo] == 1) |
|
192
|
0 |
11 |
New(0, S, cn, UV); |
|
193
|
110361 |
11 |
for (i = lo; i <= hi; i++) { |
|
194
|
15964 |
94397 |
if (nfacs[i-lo] == 1) { |
|
195
|
0 |
15964 |
if (count >= cn) |
|
196
|
0 |
0 |
Renew(S, cn += 4000, UV); |
|
210
|
100 |
1 |
for (; lo < hi; lo++) /* TODO: We should walk composites */ |
|
211
|
14 |
86 |
if (is_semiprime(lo)) |
|
213
|
0 |
1 |
if (is_semiprime(hi)) |
|
265
|
20 |
0 |
if (lo > hi || hi < 4) |
|
|
0 |
20 |
if (lo > hi || hi < 4) |
|
269
|
1 |
19 |
if (hi <= 400) return range_semiprime_sieve(0, lo, hi); |
|
271
|
14 |
5 |
if (lo <= 4) return semiprime_count(hi); |
|
275
|
1 |
4 |
if ((hi-lo+1) < hi / ((UV)isqrt(hi)*200)) { |
|
276
|
0 |
1 |
MPUverbose(2, "semiprimes %"UVuf"-%"UVuf" via iteration\n", lo, hi); |
|
280
|
3 |
1 |
if ((hi-lo+1) < hi / (isqrt(hi)/4)) { |
|
281
|
0 |
3 |
MPUverbose(2, "semiprimes %"UVuf"-%"UVuf" via sieving\n", lo, hi); |
|
284
|
0 |
1 |
MPUverbose(2, "semiprimes %"UVuf"-%"UVuf" via prime count\n", lo, hi); |
|
291
|
13 |
17898 |
if (n <= _semiprimelist[NSEMIPRIMELIST-1]) { |
|
293
|
1967 |
4 |
for (i = 0; i < NSEMIPRIMELIST-1 && n >= _semiprimelist[i+1]; i++) |
|
|
1958 |
9 |
for (i = 0; i < NSEMIPRIMELIST-1 && n >= _semiprimelist[i+1]; i++) |
|
345
|
39907 |
113 |
for (L = 3; L <= 17 && (double)n >= CROSS[L-3]; L++) ; |
|
|
22122 |
17785 |
for (L = 3; L <= 17 && (double)n >= CROSS[L-3]; L++) ; |
|
348
|
75816 |
17898 |
for (i = 1; i <= L; i++) { |
|
356
|
0 |
17898 |
if (res >= MPU_MAX_SEMI_PRIME_IDX) return MPU_MAX_SEMI_PRIME_IDX; |
|
361
|
103 |
17795 |
if ((double)res < mc) return mc; |
|
372
|
1 |
2464 |
if (n < NSEMIPRIMELIST) |
|
374
|
0 |
2464 |
if (n >= MPU_MAX_SEMI_PRIME_IDX) |
|
375
|
0 |
0 |
return n == MPU_MAX_SEMI_PRIME_IDX ? MPU_MAX_SEMI_PRIME : 0; |
|
393
|
2445 |
19 |
if (n <= (1UL<<26)) { |
|
395
|
3 |
16 |
} else if (n < (1UL<<27)) { /* Linear interpolate the two in the blend area */ |
|
398
|
14 |
2 |
} else if (logn <= 31.88477030575) { |
|
400
|
0 |
2 |
} else if (logn < 32.57791748632) { |
|
407
|
0 |
2464 |
if (est >= MPU_MAX_SEMI_PRIME) return MPU_MAX_SEMI_PRIME; |
|
416
|
15359 |
5763 |
while (!is_semiprime(++n)) |
|
421
|
14530 |
4814 |
while (!is_semiprime(--n)) |
|
429
|
226 |
2448 |
if (n < NSEMIPRIMELIST) |
|
431
|
0 |
2448 |
if (n >= MPU_MAX_SEMI_PRIME_IDX) |
|
432
|
0 |
0 |
return n == MPU_MAX_SEMI_PRIME_IDX ? MPU_MAX_SEMI_PRIME : 0; |
|
436
|
0 |
2448 |
MPUverbose(2, " using exact counts until within %"UVuf"\n",sptol); |
|
439
|
2448 |
0 |
for (gn = 2; gn < 20; gn++) { |
|
441
|
6268 |
2448 |
while (!is_semiprime(guess)) guess++; /* Guess is a semiprime */ |
|
442
|
0 |
2448 |
MPUverbose(2, " %"UVuf"-th semiprime is around %"UVuf" ... ", n, guess); |
|
445
|
0 |
2448 |
MPUverbose(2, "(%"IVdf")\n", (IV)(n-spcnt)); |
|
447
|
2298 |
150 |
if (n==spcnt || (n>spcnt && n-spcnt < sptol) || (n
|
|
|
1225 |
1073 |
if (n==spcnt || (n>spcnt && n-spcnt < sptol) || (n
|
|
|
0 |
1225 |
if (n==spcnt || (n>spcnt && n-spcnt < sptol) || (n
|
|
|
1073 |
0 |
if (n==spcnt || (n>spcnt && n-spcnt < sptol) || (n
|
|
|
0 |
1073 |
if (n==spcnt || (n>spcnt && n-spcnt < sptol) || (n
|
|
451
|
0 |
0 |
if (spcnt <= n && guess > ming) ming = guess; /* Previous guesses */ |
|
|
0 |
0 |
if (spcnt <= n && guess > ming) ming = guess; /* Previous guesses */ |
|
452
|
0 |
0 |
if (spcnt >= n && guess < maxg) maxg = guess; |
|
|
0 |
0 |
if (spcnt >= n && guess < maxg) maxg = guess; |
|
454
|
0 |
0 |
if (guess <= ming || guess >= maxg) MPUverbose(2, " fix min/max for %"UVuf"\n",n); |
|
|
0 |
0 |
if (guess <= ming || guess >= maxg) MPUverbose(2, " fix min/max for %"UVuf"\n",n); |
|
|
0 |
0 |
if (guess <= ming || guess >= maxg) MPUverbose(2, " fix min/max for %"UVuf"\n",n); |
|
455
|
0 |
0 |
if (guess <= ming) guess = ming + sptol - 1; |
|
456
|
0 |
0 |
if (guess >= maxg) guess = maxg - sptol + 1; |
|
460
|
1225 |
1223 |
if (n > spcnt && (n-spcnt) > SP_SIEVE_THRESH) { /* sieve forwards */ |
|
|
1 |
1224 |
if (n > spcnt && (n-spcnt) > SP_SIEVE_THRESH) { /* sieve forwards */ |
|
462
|
1 |
1 |
while (n > spcnt) { |
|
465
|
0 |
1 |
if (range > guess) range = guess; /* just in case */ |
|
466
|
0 |
1 |
if (range > 125000000) range = 125000000; /* Not too many at a time */ |
|
468
|
0 |
1 |
MPUverbose(2, " sieving forward %"UVuf"\n", range); |
|
470
|
0 |
1 |
if (spcnt+count <= n) { |
|
474
|
4122 |
0 |
for (i = 0; i < count && spcnt < n; i++) { |
|
|
4121 |
1 |
for (i = 0; i < count && spcnt < n; i++) { |
|
481
|
1073 |
1374 |
} else if (n < spcnt && (spcnt-n) > SP_SIEVE_THRESH) { /* sieve backwards */ |
|
|
5 |
1068 |
} else if (n < spcnt && (spcnt-n) > SP_SIEVE_THRESH) { /* sieve backwards */ |
|
483
|
5 |
5 |
while (n < spcnt) { |
|
486
|
0 |
5 |
if (range > guess) range = guess; /* just in case */ |
|
487
|
0 |
5 |
if (range > 125000000) range = 125000000; /* Not too many at a time */ |
|
489
|
0 |
5 |
MPUverbose(2, " sieving backward %"UVuf"\n", range); |
|
491
|
0 |
5 |
if (spcnt-count >= n) { |
|
495
|
9709 |
0 |
while (count > 0 && n < spcnt) { |
|
|
9704 |
5 |
while (count > 0 && n < spcnt) { |
|
505
|
4814 |
2448 |
for (; spcnt > n; spcnt--) |
|
507
|
5763 |
2448 |
for (; spcnt < n; spcnt++) |