| line |
true |
false |
branch |
|
32
|
113827 |
0 |
MPUassert(n >= primes[0] && n < primes[lastidx], "prime count via binary search out of range"); |
|
|
0 |
113827 |
MPUassert(n >= primes[0] && n < primes[lastidx], "prime count via binary search out of range"); |
|
33
|
2350707 |
113827 |
while (i < j) { |
|
35
|
848623 |
1502084 |
if (primes[mid] <= n) i = mid+1; |
|
47
|
12 |
2558 |
if (n > 1000000) { /* Upfront work to speed up the many small calls */ |
|
49
|
3 |
9 |
if (nprecalc > _MPU_LMO_CROSSOVER) nprecalc = _MPU_LMO_CROSSOVER; |
|
55
|
2570 |
0 |
if (sqrtn >= 2) sum += LMO_prime_count(n/2) - pc++; |
|
56
|
2570 |
0 |
if (sqrtn >= 3) sum += LMO_prime_count(n/3) - pc++; |
|
57
|
2570 |
0 |
if (sqrtn >= 5) sum += LMO_prime_count(n/5) - pc++; |
|
58
|
2570 |
0 |
if (sqrtn >= 7) { |
|
62
|
2570 |
2570 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
63
|
158555 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
2570 |
155985 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
155985 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
158555 |
5346 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
7916 |
2570 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
65
|
113827 |
42158 |
if (np < xlim) { |
|
66
|
113815 |
12 |
if (xarr == 0 || np < xbeg) { |
|
|
0 |
113815 |
if (xarr == 0 || np < xbeg) { |
|
67
|
0 |
12 |
if (xarr != 0) { Safefree(xarr); xarr = 0; } |
|
70
|
0 |
12 |
if (xend - xbeg > xmax) xbeg = xend - xmax; |
|
84
|
12 |
2558 |
if (xarr != 0) { Safefree(xarr); xarr = 0; } |
|
105
|
0 |
27 |
if (lo < 4) lo = 4; |
|
106
|
0 |
27 |
if (hi > MPU_MAX_SEMI_PRIME) hi = MPU_MAX_SEMI_PRIME; |
|
108
|
16 |
11 |
if (hi <= _semiprimelist[NSEMIPRIMELIST-1]) { |
|
109
|
1 |
15 |
if (semis == 0) { |
|
110
|
11 |
0 |
for (i = 1; i < NSEMIPRIMELIST && _semiprimelist[i] <= hi; i++) |
|
|
10 |
1 |
for (i = 1; i < NSEMIPRIMELIST && _semiprimelist[i] <= hi; i++) |
|
111
|
6 |
4 |
if (_semiprimelist[i] >= lo) |
|
115
|
123 |
0 |
for (i = 1; i < NSEMIPRIMELIST && _semiprimelist[i] <= hi; i++) |
|
|
108 |
15 |
for (i = 1; i < NSEMIPRIMELIST && _semiprimelist[i] <= hi; i++) |
|
116
|
58 |
50 |
if (_semiprimelist[i] >= lo) |
|
124
|
11 |
0 |
if (sqrtn*sqrtn < hi && sqrtn < (UVCONST(1)<<(BITS_PER_WORD/2))-1) sqrtn++; |
|
|
11 |
0 |
if (sqrtn*sqrtn < hi && sqrtn < (UVCONST(1)<<(BITS_PER_WORD/2))-1) sqrtn++; |
|
126
|
11 |
0 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
33 |
15613 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
22 |
11 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
11 |
11 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
4557 |
11056 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
1 |
4569 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
13 |
4556 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
1 |
4556 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
0 |
15612 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
|
10 |
15635 |
START_DO_FOR_EACH_PRIME(2, cutn) { |
|
127
|
15623 |
12 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
15605 |
18 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
728033 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
712398 |
15635 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
2405 |
13230 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
13224 |
6 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
141152 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
125517 |
15635 |
MARKSEMI(p,nfacs,lo,hi); |
|
129
|
2 |
9 |
if (cutn < sqrtn) { |
|
133
|
2 |
2 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
134
|
24021 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
2 |
24019 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
24019 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
24021 |
1153 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
1155 |
2 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
135
|
24019 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
24019 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
58489 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
34470 |
24019 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
8238 |
15781 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
15781 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
24019 |
0 |
MARKSEMI(p,nfacs,lo,hi); |
|
|
0 |
24019 |
MARKSEMI(p,nfacs,lo,hi); |
|
140
|
1 |
10 |
if (semis == 0) { |
|
141
|
34588 |
1 |
for (i = lo; i <= hi; i++) |
|
142
|
5802 |
28786 |
if (nfacs[i-lo] == 1) |
|
146
|
0 |
10 |
New(0, S, cn, UV); |
|
147
|
242986 |
10 |
for (i = lo; i <= hi; i++) { |
|
148
|
34981 |
208005 |
if (nfacs[i-lo] == 1) { |
|
149
|
0 |
34981 |
if (count >= cn) |
|
150
|
0 |
0 |
Renew(S, cn += 4000, UV); |
|
164
|
0 |
0 |
for (; lo < hi; lo++) /* TODO: We should walk composites */ |
|
165
|
0 |
0 |
if (is_semiprime(lo)) |
|
167
|
0 |
0 |
if (is_semiprime(hi)) |
|
219
|
16 |
0 |
if (lo > hi || hi < 4) |
|
|
0 |
16 |
if (lo > hi || hi < 4) |
|
223
|
1 |
15 |
if (hi <= 400) return range_semiprime_sieve(0, lo, hi); |
|
225
|
14 |
1 |
if (lo <= 4) return _semiprime_count(hi); |
|
229
|
0 |
1 |
if ((hi-lo+1) < hi / (isqrt(hi)*200)) { |
|
230
|
0 |
0 |
MPUverbose(2, "semiprimes %"UVuf"-%"UVuf" via iteration\n", lo, hi); |
|
234
|
1 |
0 |
if ((hi-lo+1) < hi / (isqrt(hi)/4)) { |
|
235
|
0 |
1 |
MPUverbose(2, "semiprimes %"UVuf"-%"UVuf" via sieving\n", lo, hi); |
|
238
|
0 |
0 |
MPUverbose(2, "semiprimes %"UVuf"-%"UVuf" via prime count\n", lo, hi); |
|
243
|
1 |
23 |
if (n <= _semiprimelist[NSEMIPRIMELIST-1]) { |
|
245
|
2 |
0 |
while (i < NSEMIPRIMELIST-1 && n >= _semiprimelist[i+1]) |
|
|
1 |
1 |
while (i < NSEMIPRIMELIST-1 && n >= _semiprimelist[i+1]) |
|
254
|
0 |
23 |
if (1.05*init >= (double)UV_MAX) |
|
258
|
540 |
23 |
while (lo < hi) { |
|
260
|
281 |
259 |
if (nth_semiprime_approx(mid) < n) lo = mid+1; |
|
270
|
0 |
3115 |
if (n < NSEMIPRIMELIST) |
|
285
|
2807 |
308 |
if (n <= (1UL<<26)) { |
|
287
|
51 |
257 |
} else if (n < (1UL<<27)) { /* Linear interpolate the two in the blend area */ |
|
290
|
198 |
59 |
} else if (logn <= 31.88477030575) { |
|
292
|
0 |
59 |
} else if (logn < 32.57791748632) { |
|
299
|
0 |
3115 |
if (est >= UV_MAX) return 0; |
|
304
|
1557 |
578 |
while (!is_semiprime(++n)) |
|
309
|
43710 |
14233 |
while (!is_semiprime(--n)) |
|
317
|
116 |
2555 |
if (n < NSEMIPRIMELIST) |
|
322
|
0 |
2555 |
MPUverbose(2, " using exact counts until within %"UVuf"\n",sptol); |
|
325
|
2556 |
0 |
for (gn = 2; gn < 20; gn++) { |
|
327
|
6503 |
2556 |
while (!is_semiprime(guess)) guess++; /* Guess is a semiprime */ |
|
328
|
0 |
2556 |
MPUverbose(2, " %"UVuf"-th semiprime is around %"UVuf" ... ", n, guess); |
|
331
|
0 |
2556 |
MPUverbose(2, "(%"IVdf")\n", (IV)(n-spcnt)); |
|
333
|
2444 |
112 |
if (n==spcnt || (n>spcnt && n-spcnt < sptol) || (n
|
|
|
231 |
2213 |
if (n==spcnt || (n>spcnt && n-spcnt < sptol) || (n
|
|
|
1 |
230 |
if (n==spcnt || (n>spcnt && n-spcnt < sptol) || (n
|
|
|
2213 |
1 |
if (n==spcnt || (n>spcnt && n-spcnt < sptol) || (n
|
|
|
0 |
2213 |
if (n==spcnt || (n>spcnt && n-spcnt < sptol) || (n
|
|
337
|
1 |
0 |
if (spcnt <= n && guess > ming) ming = guess; /* Previous guesses */ |
|
|
1 |
0 |
if (spcnt <= n && guess > ming) ming = guess; /* Previous guesses */ |
|
338
|
0 |
1 |
if (spcnt >= n && guess < maxg) maxg = guess; |
|
|
0 |
0 |
if (spcnt >= n && guess < maxg) maxg = guess; |
|
340
|
1 |
0 |
if (guess <= ming || guess >= maxg) MPUverbose(2, " fix min/max for %"UVuf"\n",n); |
|
|
0 |
1 |
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); |
|
341
|
0 |
1 |
if (guess <= ming) guess = ming + sptol - 1; |
|
342
|
0 |
1 |
if (guess >= maxg) guess = maxg - sptol + 1; |
|
346
|
230 |
2325 |
if (n > spcnt && (n-spcnt) > SP_SIEVE_THRESH) { /* sieve forwards */ |
|
|
2 |
228 |
if (n > spcnt && (n-spcnt) > SP_SIEVE_THRESH) { /* sieve forwards */ |
|
348
|
2 |
2 |
while (n > spcnt) { |
|
351
|
0 |
2 |
if (range > guess) range = guess; /* just in case */ |
|
352
|
0 |
2 |
if (range > 125000000) range = 125000000; /* Not too many at a time */ |
|
354
|
0 |
2 |
MPUverbose(2, " sieving forward %"UVuf"\n", range); |
|
356
|
0 |
2 |
if (spcnt+count <= n) { |
|
360
|
21087 |
0 |
for (i = 0; i < count && spcnt < n; i++) { |
|
|
21085 |
2 |
for (i = 0; i < count && spcnt < n; i++) { |
|
367
|
2213 |
340 |
} else if (n < spcnt && (spcnt-n) > SP_SIEVE_THRESH) { /* sieve backwards */ |
|
|
5 |
2208 |
} else if (n < spcnt && (spcnt-n) > SP_SIEVE_THRESH) { /* sieve backwards */ |
|
369
|
5 |
5 |
while (n < spcnt) { |
|
372
|
0 |
5 |
if (range > guess) range = guess; /* just in case */ |
|
373
|
0 |
5 |
if (range > 125000000) range = 125000000; /* Not too many at a time */ |
|
375
|
0 |
5 |
MPUverbose(2, " sieving backward %"UVuf"\n", range); |
|
377
|
0 |
5 |
if (spcnt-count >= n) { |
|
381
|
10260 |
0 |
while (count > 0 && n < spcnt) { |
|
|
10255 |
5 |
while (count > 0 && n < spcnt) { |
|
391
|
14233 |
2555 |
for (; spcnt > n; spcnt--) |
|
393
|
578 |
2555 |
for (; spcnt < n; spcnt++) |