Branch Coverage

prime_nth_count.c
Criterion Covered Total %
branch 387 548 70.6


line true false branch
86 35065 37339 if (nbytes >= 16) {
87 224578 35065 while ( word_unaligned(m,sizeof(UV)) && nbytes--)
224578 0 while ( word_unaligned(m,sizeof(UV)) && nbytes--)
89 35065 0 if (nbytes >= 8) {
95 376444 35065 while (nwords--)
101 309411 72404 while (nbytes--)
120 0 1085 MPUassert(sieve != 0, "count_segment_maxcount incorrect args");
121 0 1085 MPUassert(pos != 0, "count_segment_maxcount incorrect args");
123 1085 0 if ( (nbytes == 0) || (maxcount == 0) )
0 1085 if ( (nbytes == 0) || (maxcount == 0) )
127 3416 1085 while ((count+64) < maxcount && sieveptr < maxsieve) {
3416 0 while ((count+64) < maxcount && sieveptr < maxsieve) {
129 109 3307 UV div = (top < 8000) ? 8 : /* 8 cannot overcount */
20 89 UV div = (top < 8000) ? 8 : /* 8 cannot overcount */
6 14 UV div = (top < 8000) ? 8 : /* 8 cannot overcount */
133 0 3416 if (minbytes > (UV)(maxsieve-sieveptr)) minbytes = maxsieve-sieveptr;
138 15194 0 while ( (sieveptr < maxsieve) && (count < maxcount) )
14109 1085 while ( (sieveptr < maxsieve) && (count < maxcount) )
141 1085 1085 while (count >= maxcount)
146 0 1085 MPUassert(count < maxcount, "count_segment_maxcount wrong count");
148 0 1085 if (byte == nbytes)
152 16689 0 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, byte*30+1, nbytes*30-1)
0 16689 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, byte*30+1, nbytes*30-1)
2772 13917 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, byte*30+1, nbytes*30-1)
16689 0 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, byte*30+1, nbytes*30-1)
1085 0 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, byte*30+1, nbytes*30-1)
153 1085 1687 if (++count == maxcount) { *pos = p; return count; }
167 0 71444 MPUassert( sieve != 0, "count_segment_ranged incorrect args");
168 0 71444 if (nbytes == 0) return 0;
173 0 71444 if (hi_d >= nbytes) {
178 0 71444 if (highp < lowp)
192 69624 1820 if (lo_m > 1) {
194 556377 0 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, upper)
69616 486761 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, upper)
486728 33 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, upper)
556377 8 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, upper)
69624 69624 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, upper)
200 352 71092 if (highp < lowp)
207 68988 2104 if (count_bytes > 0) {
212 4923 66169 if (highp < lowp)
216 1420445 0 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, highp)
65752 1354693 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, highp)
164714 1189979 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, highp)
1420445 417 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, highp)
66169 66169 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, highp)
269 71470 18 if ((low <= 2) && (high >= 2)) count++;
71448 22 if ((low <= 2) && (high >= 2)) count++;
270 71472 16 if ((low <= 3) && (high >= 3)) count++;
71443 29 if ((low <= 3) && (high >= 3)) count++;
271 71474 14 if ((low <= 5) && (high >= 5)) count++;
71433 41 if ((low <= 5) && (high >= 5)) count++;
272 71474 14 if (low < 7) low = 7;
274 53 71435 if (low > high) return count;
277 71422 13 if (low == 7 && high <= 30*NPRIME_SIEVE30) {
69611 1811 if (low == 7 && high <= 30*NPRIME_SIEVE30) {
288 1811 13 APPLY_TABLES
1811 0 APPLY_TABLES
937 874 APPLY_TABLES
9575 937 APPLY_TABLES
9575 0 APPLY_TABLES
202 672 APPLY_TABLES
35731 202 APPLY_TABLES
35731 0 APPLY_TABLES
264 408 APPLY_TABLES
112175 264 APPLY_TABLES
112175 0 APPLY_TABLES
225 183 APPLY_TABLES
87421 225 APPLY_TABLES
87421 0 APPLY_TABLES
183 0 APPLY_TABLES
82929 183 APPLY_TABLES
82929 0 APPLY_TABLES
0 0 APPLY_TABLES
0 0 APPLY_TABLES
0 0 APPLY_TABLES
0 0 APPLY_TABLES
0 0 APPLY_TABLES
297 96 1728 if (segment_size < high_d) {
299 96 0 UV endp = (high_d >= (UV_MAX/30)) ? UV_MAX-2 : 30*high_d+29;
304 1824 0 if ( (segment_size > 0) && (low_d <= segment_size) ) {
1728 96 if ( (segment_size > 0) && (low_d <= segment_size) ) {
308 1728 0 if (high_d < segment_size) {
314 0 0 if (30*low_d > low) low = 30*low_d;
322 105 96 while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) {
334 685 0 if (lo > hi || hi < 2)
1 684 if (lo > hi || hi < 2)
342 655 29 if (hi < _MPU_LMO_CROSSOVER) return segment_prime_count(lo, hi);
346 10 19 if ( (hi-lo+1) < range_threshold )
349 19 0 return LMO_prime_count(hi) - ((lo < 2) ? 0 : LMO_prime_count(lo-1));
354 11 25 if (n < 3000000) return segment_prime_count(2, n);
363 407 216 if (n < 2000) return twin_prime_count(3,n);
372 86 130 if (n < 32000000) {
374 0 86 if (n < 4000) fm = 0.2952;
375 1 85 else if (n < 8000) fm = 0.3152;
376 0 85 else if (n < 16000) fm = 0.3090;
377 15 70 else if (n < 32000) fm = 0.3096;
378 14 56 else if (n < 64000) fm = 0.3100;
379 15 41 else if (n < 128000) fm = 0.3089;
380 0 41 else if (n < 256000) fm = 0.3099;
381 19 22 else if (n < 600000) fm = .3091 + (n-256000) * (.3056-.3091) / (600000-256000);
382 0 22 else if (n < 1000000) fm = .3062 + (n-600000) * (.3042-.3062) / (1000000-600000);
383 0 22 else if (n < 4000000) fm = .3067 + (n-1000000) * (.3041-.3067) / (4000000-1000000);
384 22 0 else if (n <16000000) fm = .3033 + (n-4000000) * (.2983-.3033) / (16000000-4000000);
396 15471 998 if (n < 33000) return segment_prime_count(2, n);
405 142 856 if (n <= 300000) { /* Quite accurate and avoids calling Li for speed. */
406 113 29 a = (n < 70200) ? 947 : (n < 176000) ? 904 : 829;
102 11 a = (n < 70200) ? 947 : (n < 176000) ? 904 : 829;
408 837 19 } else if (n < UVCONST(4000000000)) {
411 837 0 : (n < 300000) ? -3.0L
412 837 0 : (n < 303000) ? 5.0L
413 837 0 : (n < 1100000) ? -7.0L
414 547 290 : (n < 4500000) ? -37.0L
415 34 513 : (n < 10200000) ? -70.0L
416 8 26 : (n < 36900000) ? -53.0L
417 7 1 : (n < 38100000) ? -29.0L
418 0 7 : -84.0L;
420 17 2 } else if (fn < 1e19) { /* Büthe 2015 1.9 1511.02032v1.pdf */
463 3727 582 if (n < 33000) return segment_prime_count(2, n);
475 561 21 if (BITS_PER_WORD == 32 || fn <= 821800000.0) { /* Dusart 2010, page 2 */
476 1839 0 for (i = 0; i < (int)NUPPER_THRESH; i++)
477 561 1278 if (n < _upper_thresh[i].thresh)
479 561 0 a = (i < (int)NUPPER_THRESH) ? _upper_thresh[i].aval : 2.334L;
481 19 2 } else if (fn < 1e19) { /* Büthe 2015 1.10 Skewes number lower limit */
482 1 18 a = (fn < 1100000000.0) ? 0.032 /* Empirical */
3 15 a = (fn < 1100000000.0) ? 0.032 /* Empirical */
2 13 a = (fn < 1100000000.0) ? 0.032 /* Empirical */
494 2047 957 const long double a = (n < 228) ? .6483 : (n < 948) ? .8032 : (n < 2195) ? .8800 : (n < 39017) ? .9019 : .9484;
730 227 const long double a = (n < 228) ? .6483 : (n < 948) ? .8032 : (n < 2195) ? .8800 : (n < 39017) ? .9019 : .9484;
91 136 const long double a = (n < 228) ? .6483 : (n < 948) ? .8032 : (n < 2195) ? .8800 : (n < 39017) ? .9019 : .9484;
21 115 const long double a = (n < 228) ? .6483 : (n < 948) ? .8032 : (n < 2195) ? .8800 : (n < 39017) ? .9019 : .9484;
497 0 3004 if (*hi < *lo) *hi = MPU_MAX_PRIME;
505 429 2498 if (n < NPRIMES_SMALL)
512 2406 92 if (n < 688383) {
515 15954 2406 while (lo < hi) {
517 7821 8133 if (prime_count_lower(mid) < n) lo = mid+1;
525 12 80 if (n >= 46254381) {
528 61 19 } else if (n >= 8009824) {
533 0 92 if (upper >= (long double)UV_MAX) {
534 0 0 if (n <= MPU_MAX_PRIME_IDX) return MPU_MAX_PRIME;
546 638 675 if (n < NPRIMES_SMALL)
554 598 77 if (n < 2000000) {
557 3794 598 while (lo < hi) {
559 1924 1870 if (prime_count_upper(mid) < n) lo = mid+1;
566 67 10 double b1 = (n < 56000000) ? 11.200 : 11.508;
575 2 23 return (n < NPRIMES_SMALL) ? primes_small[n] : inverse_R(n);
586 5538 1088 if (n < NPRIMES_SMALL)
591 0 1088 MPUassert(upper_limit > 0, "nth_prime got an upper limit of 0");
600 24 1064 if (upper_limit <= get_prime_cache(0, 0) || upper_limit <= 32*1024*30) {
2 22 if (upper_limit <= get_prime_cache(0, 0) || upper_limit <= 32*1024*30) {
604 1066 0 if (segment_size > 0)
625 3 19 if (count >= n) { /* Too far. Walk backwards */
626 0 3 if (is_prime(lower_limit)) count--;
627 4 3 for (p = 0; p <= (count-n); p++)
637 1066 19 if (count == target)
644 19 19 while (count < target) {
646 18 1 if ( (30*(segbase+segment_size)+29) > upper_limit )
655 0 19 if (count < target)
659 0 19 MPUassert(count == target, "nth_prime got incorrect count");
700 416 2 if (beg <= 3 && end >= 10000000) {
6 410 if (beg <= 3 && end >= 10000000) {
702 40 0 for (exp = 0; exp < twin_num_exponents && end >= base; exp++) {
34 6 for (exp = 0; exp < twin_num_exponents && end >= base; exp++) {
703 284 28 for (mult = 1; mult < 10 && end >= mult*base; mult++) {
278 6 for (mult = 1; mult < 10 && end >= mult*base; mult++) {
706 0 278 if (exp == twin_num_exponents-1 && mult >= twin_last_mult) break;
0 0 if (exp == twin_num_exponents-1 && mult >= twin_last_mult) break;
711 410 8 if (beg <= 3 && end >= 3) sum++;
410 0 if (beg <= 3 && end >= 3) sum++;
712 410 8 if (beg <= 5 && end >= 5) sum++;
410 0 if (beg <= 5 && end >= 5) sum++;
713 410 8 if (beg < 11) beg = 7;
714 418 0 if (beg <= end) {
719 4974 418 while ((beg % 30) != 1) {
720 2876 2098 if (is_prime(beg) && is_prime(beg+2) && beg <= end) sum++;
1232 1644 if (is_prime(beg) && is_prime(beg+2) && beg <= end) sum++;
1232 0 if (is_prime(beg) && is_prime(beg+2) && beg <= end) sum++;
723 2861 403 while ((end % 30) != 29) {
724 904 1957 if (is_prime(end) && is_prime(end+2) && beg <= end) sum++;
179 725 if (is_prime(end) && is_prime(end+2) && beg <= end) sum++;
179 0 if (is_prime(end) && is_prime(end+2) && beg <= end) sum++;
725 15 2846 end -= 2; if (beg > end) break;
728 403 15 if (beg <= end) {
731 403 403 while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) {
736 53313 403 while (sp < spend) {
738 7513 45800 if (!(s & 0x0C)) sum++;
739 5920 47393 if (!(s & 0x30)) sum++;
740 18470 34843 if (!(s & 0x80) && !(*sp & 0x01)) sum++;
6819 11651 if (!(s & 0x80) && !(*sp & 0x01)) sum++;
743 148 255 if (!(s & 0x0C)) sum++;
744 100 303 if (!(s & 0x30)) sum++;
745 258 145 if (!(s & 0x80) && is_prime(seg_high+2)) sum++;
172 86 if (!(s & 0x80) && is_prime(seg_high+2)) sum++;
759 6 48 if (n < 6) {
774 48 0 if (dend < (double)end) end = (UV) dend;
777 0 48 if (n > 58980) { /* Use twin_prime_count tables to accelerate if possible */
779 0 0 for (exp = 0; exp < twin_num_exponents && end >= base; exp++) {
0 0 for (exp = 0; exp < twin_num_exponents && end >= base; exp++) {
780 0 0 for (mult = 1; mult < 10 && n > twin_steps[step]; mult++) {
0 0 for (mult = 1; mult < 10 && n > twin_steps[step]; mult++) {
783 0 0 if (exp == twin_num_exponents-1 && mult >= twin_last_mult) break;
0 0 if (exp == twin_num_exponents-1 && mult >= twin_last_mult) break;
788 48 0 if (beg == 2) { beg = 31; n -= 5; }
793 48 48 while (n && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) {
48 0 while (n && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) {
796 4428 0 for (p = 0; p < bytes; p++) {
798 4428 0 if (p+1 < bytes) s |= (((UV)segment[p+1]) << 8);
799 0 0 else if (!is_prime(seg_high+2)) s |= 0xFF00;
800 853 3575 if (!(s & 0x000C) && !--n) { nth=seg_base+p*30+11; break; }
19 834 if (!(s & 0x000C) && !--n) { nth=seg_base+p*30+11; break; }
801 686 3723 if (!(s & 0x0030) && !--n) { nth=seg_base+p*30+17; break; }
13 673 if (!(s & 0x0030) && !--n) { nth=seg_base+p*30+17; break; }
802 783 3613 if (!(s & 0x0180) && !--n) { nth=seg_base+p*30+29; break; }
16 767 if (!(s & 0x0180) && !--n) { nth=seg_base+p*30+29; break; }
817 1 57 if (n < 6)
825 0 57 hi = (UV) ( (n >= 1e16) ? (1.04 * fnlog2n) :
0 57 hi = (UV) ( (n >= 1e16) ? (1.04 * fnlog2n) :
2 55 hi = (UV) ( (n >= 1e16) ? (1.04 * fnlog2n) :
5 50 hi = (UV) ( (n >= 1e16) ? (1.04 * fnlog2n) :
830 0 57 if (hi <= lo) hi = UV_MAX;
831 616 57 while (lo < hi) {
833 329 287 if (twin_prime_count_approx(mid) < fn) lo = mid+1;
911 0 0 New(0, V, r2+1, uint128_t);
912 0 0 New(0, S, r2+1, uint128_t);
913 0 0 for (k = 0; k <= r2; k++) {
914 0 0 uint128_t v = (k <= r) ? k : n/(r2-k+1);
919 0 0 START_DO_FOR_EACH_PRIME(2, r) {
0 0 START_DO_FOR_EACH_PRIME(2, r) {
0 0 START_DO_FOR_EACH_PRIME(2, r) {
0 0 START_DO_FOR_EACH_PRIME(2, r) {
0 0 START_DO_FOR_EACH_PRIME(2, r) {
0 0 START_DO_FOR_EACH_PRIME(2, r) {
0 0 START_DO_FOR_EACH_PRIME(2, r) {
0 0 START_DO_FOR_EACH_PRIME(2, r) {
0 0 START_DO_FOR_EACH_PRIME(2, r) {
0 0 START_DO_FOR_EACH_PRIME(2, r) {
921 0 0 for (j = k-1; j > 1 && V[j] >= p2; j--) {
0 0 for (j = k-1; j > 1 && V[j] >= p2; j--) {
923 0 0 if (a > r) a = r2 - n/a + 1;
924 0 0 if (b > r) b = r2 - n/b + 1;
941 1000 3 if ((low <= 2) && (high >= 2)) sum += 2;
1000 0 if ((low <= 2) && (high >= 2)) sum += 2;
942 1000 3 if ((low <= 3) && (high >= 3)) sum += 3;
999 1 if ((low <= 3) && (high >= 3)) sum += 3;
943 1000 3 if ((low <= 5) && (high >= 5)) sum += 5;
997 3 if ((low <= 5) && (high >= 5)) sum += 5;
944 1000 3 if (low < 7) low = 7;
948 1000 3 if (low == 7 && high >= 29505444491) return 0;
0 1000 if (low == 7 && high >= 29505444491) return 0;
949 0 1003 if (low >= 1e10 && (high-low) >= 32e9) return 0;
0 0 if (low >= 1e10 && (high-low) >= 32e9) return 0;
950 0 1003 if (low >= 1e13 && (high-low) >= 5e7) return 0;
0 0 if (low >= 1e13 && (high-low) >= 5e7) return 0;
956 1000 3 if (low == 7 && high >= 2e8) {
0 1000 if (low == 7 && high >= 2e8) {
958 0 0 for (step = 1; high >= (step * 2e8) && step < N_SUM_TABLE; step++) {
0 0 for (step = 1; high >= (step * 2e8) && step < N_SUM_TABLE; step++) {
965 998 5 if (low <= high) {
969 1996 0 while (!overflow && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) {
998 998 while (!overflow && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) {
978 2005 0 for (i = 0; i < 8 && p+wheel30[i] < low; i++)
1007 998 for (i = 0; i < 8 && p+wheel30[i] < low; i++)
979 3 1004 if ( (*sp & (1<
983 7984 998 for (i = 0; i < 8; i++)
984 4908 3076 if ( (*spend & (1< high )
2459 2449 if ( (*spend & (1< high )
987 28641 998 while (sp <= spend) {
989 28641 0 if (sum < (UV_MAX >> 3) && pbase < (UV_MAX >> 5)) {
28641 0 if (sum < (UV_MAX >> 3) && pbase < (UV_MAX >> 5)) {
994 0 0 for (i = 0; i < byte_zeros[s]; i++) {
995 0 0 if (sum+pbase < sum) overflow = 1;
998 0 0 if (sum+byte_sum[s] < sum) overflow = 1;
1000 0 0 if (overflow) break;
1007 1003 0 if (!overflow && return_sum != 0) *return_sum = sum;
1003 0 if (!overflow && return_sum != 0) *return_sum = sum;