Branch Coverage

prime_nth_count.c
Criterion Covered Total %
branch 388 548 70.8


line true false branch
86 21132 2116 if (nbytes >= 16) {
87 135659 21132 while ( word_unaligned(m,sizeof(UV)) && nbytes--)
135659 0 while ( word_unaligned(m,sizeof(UV)) && nbytes--)
89 21132 0 if (nbytes >= 8) {
95 278221 21132 while (nwords--)
101 93938 23248 while (nbytes--)
120 0 1086 MPUassert(sieve != 0, "count_segment_maxcount incorrect args");
121 0 1086 MPUassert(pos != 0, "count_segment_maxcount incorrect args");
123 1086 0 if ( (nbytes == 0) || (maxcount == 0) )
0 1086 if ( (nbytes == 0) || (maxcount == 0) )
127 3413 1086 while ((count+64) < maxcount && sieveptr < maxsieve) {
3413 0 while ((count+64) < maxcount && sieveptr < maxsieve) {
129 109 3304 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 3413 if (minbytes > (UV)(maxsieve-sieveptr)) minbytes = maxsieve-sieveptr;
138 15194 0 while ( (sieveptr < maxsieve) && (count < maxcount) )
14108 1086 while ( (sieveptr < maxsieve) && (count < maxcount) )
141 1086 1086 while (count >= maxcount)
146 0 1086 MPUassert(count < maxcount, "count_segment_maxcount wrong count");
148 0 1086 if (byte == nbytes)
152 16700 0 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, byte*30+1, nbytes*30-1)
0 16700 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, byte*30+1, nbytes*30-1)
2774 13926 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, byte*30+1, nbytes*30-1)
16700 0 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, byte*30+1, nbytes*30-1)
1086 0 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, byte*30+1, nbytes*30-1)
153 1086 1688 if (++count == maxcount) { *pos = p; return count; }
167 0 21715 MPUassert( sieve != 0, "count_segment_ranged incorrect args");
168 0 21715 if (nbytes == 0) return 0;
173 0 21715 if (hi_d >= nbytes) {
178 0 21715 if (highp < lowp)
192 21599 116 if (lo_m > 1) {
194 170205 0 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, upper)
21591 148614 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, upper)
148565 49 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, upper)
170205 8 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, upper)
21599 21599 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, upper)
200 1340 20375 if (highp < lowp)
207 19835 540 if (count_bytes > 0) {
212 1533 18842 if (highp < lowp)
216 324221 0 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, highp)
18633 305588 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, highp)
41206 264382 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, highp)
324221 209 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, highp)
18842 18842 START_DO_FOR_EACH_SIEVE_PRIME(sieve, 0, lowp, highp)
269 21752 16 if ((low <= 2) && (high >= 2)) count++;
21730 22 if ((low <= 2) && (high >= 2)) count++;
270 21753 15 if ((low <= 3) && (high >= 3)) count++;
21724 29 if ((low <= 3) && (high >= 3)) count++;
271 21755 13 if ((low <= 5) && (high >= 5)) count++;
21714 41 if ((low <= 5) && (high >= 5)) count++;
272 21755 13 if (low < 7) low = 7;
274 53 21715 if (low > high) return count;
276 21702 13 if (low == 7 && high <= 30*NPRIME_SIEVE30) {
21434 268 if (low == 7 && high <= 30*NPRIME_SIEVE30) {
287 268 13 APPLY_TABLES
116 152 APPLY_TABLES
60 56 APPLY_TABLES
983 60 APPLY_TABLES
983 0 APPLY_TABLES
39 17 APPLY_TABLES
5898 39 APPLY_TABLES
5898 0 APPLY_TABLES
6 11 APPLY_TABLES
1965 6 APPLY_TABLES
1965 0 APPLY_TABLES
4 7 APPLY_TABLES
107 4 APPLY_TABLES
107 0 APPLY_TABLES
7 0 APPLY_TABLES
1895 7 APPLY_TABLES
1895 0 APPLY_TABLES
0 0 APPLY_TABLES
0 0 APPLY_TABLES
0 0 APPLY_TABLES
0 0 APPLY_TABLES
0 0 APPLY_TABLES
295 46 235 if (segment_size < high_d) {
297 46 0 UV endp = (high_d >= (UV_MAX/30)) ? UV_MAX-2 : 30*high_d+29;
302 281 0 if ( (segment_size > 0) && (low_d <= segment_size) ) {
235 46 if ( (segment_size > 0) && (low_d <= segment_size) ) {
306 235 0 if (high_d < segment_size) {
312 0 0 if (30*low_d > low) low = 30*low_d;
320 46 46 while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) {
334 683 0 if (lo > hi || hi < 2)
1 682 if (lo > hi || hi < 2)
338 653 29 if (hi < 66000000) return segment_prime_count(lo, hi);
342 10 19 if ( (hi-lo+1) < range_threshold )
345 19 0 return LMO_prime_count(hi) - ((lo < 2) ? 0 : LMO_prime_count(lo-1));
352 11 25 if (n < 3000000) return segment_prime_count(2, n);
361 407 216 if (n < 2000) return twin_prime_count(3,n);
370 86 130 if (n < 32000000) {
372 0 86 if (n < 4000) fm = 0.2952;
373 1 85 else if (n < 8000) fm = 0.3152;
374 0 85 else if (n < 16000) fm = 0.3090;
375 15 70 else if (n < 32000) fm = 0.3096;
376 14 56 else if (n < 64000) fm = 0.3100;
377 15 41 else if (n < 128000) fm = 0.3089;
378 0 41 else if (n < 256000) fm = 0.3099;
379 19 22 else if (n < 600000) fm = .3091 + (n-256000) * (.3056-.3091) / (600000-256000);
380 0 22 else if (n < 1000000) fm = .3062 + (n-600000) * (.3042-.3062) / (1000000-600000);
381 0 22 else if (n < 4000000) fm = .3067 + (n-1000000) * (.3041-.3067) / (4000000-1000000);
382 22 0 else if (n <16000000) fm = .3033 + (n-4000000) * (.2983-.3033) / (16000000-4000000);
394 15470 979 if (n < 33000) return segment_prime_count(2, n);
400 138 841 if (n <= 300000) { /* Quite accurate and avoids calling Li for speed. */
401 109 29 a = (n < 70200) ? 947 : (n < 176000) ? 904 : 829;
99 10 a = (n < 70200) ? 947 : (n < 176000) ? 904 : 829;
403 822 19 } else if (n < UVCONST(4000000000)) {
406 822 0 : (n < 300000) ? -3.0L
407 822 0 : (n < 303000) ? 5.0L
408 822 0 : (n < 1100000) ? -7.0L
409 547 275 : (n < 4500000) ? -37.0L
410 34 513 : (n < 10200000) ? -70.0L
411 8 26 : (n < 36900000) ? -53.0L
412 7 1 : (n < 38100000) ? -29.0L
413 0 7 : -84.0L;
415 17 2 } else if (fn < 1e19) { /* Büthe 2015 1.9 1511.02032v1.pdf */
458 5544 600 if (n < 33000) return segment_prime_count(2, n);
464 579 21 if (BITS_PER_WORD == 32 || fn <= 821800000.0) { /* Dusart 2010, page 2 */
465 1866 0 for (i = 0; i < (int)NUPPER_THRESH; i++)
466 579 1287 if (n < _upper_thresh[i].thresh)
468 579 0 a = (i < (int)NUPPER_THRESH) ? _upper_thresh[i].aval : 2.334L;
470 19 2 } else if (fn < 1e19) { /* Büthe 2015 1.10 Skewes number lower limit */
471 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 */
483 2048 956 const long double a = (n < 228) ? .6483 : (n < 948) ? .8032 : (n < 2195) ? .8800 : (n < 39017) ? .9019 : .9484;
731 225 const long double a = (n < 228) ? .6483 : (n < 948) ? .8032 : (n < 2195) ? .8800 : (n < 39017) ? .9019 : .9484;
90 135 const long double a = (n < 228) ? .6483 : (n < 948) ? .8032 : (n < 2195) ? .8800 : (n < 39017) ? .9019 : .9484;
21 114 const long double a = (n < 228) ? .6483 : (n < 948) ? .8032 : (n < 2195) ? .8800 : (n < 39017) ? .9019 : .9484;
486 0 3004 if (*hi < *lo) *hi = MPU_MAX_PRIME;
494 429 2498 if (n < NPRIMES_SMALL)
501 2406 92 if (n < 688383) {
504 15946 2406 while (lo < hi) {
506 7815 8131 if (prime_count_lower(mid) < n) lo = mid+1;
514 12 80 if (n >= 46254381) {
517 61 19 } else if (n >= 8009824) {
522 0 92 if (upper >= (long double)UV_MAX) {
523 0 0 if (n <= MPU_MAX_PRIME_IDX) return MPU_MAX_PRIME;
535 638 675 if (n < NPRIMES_SMALL)
543 598 77 if (n < 2000000) {
546 3794 598 while (lo < hi) {
548 1924 1870 if (prime_count_upper(mid) < n) lo = mid+1;
555 67 10 double b1 = (n < 56000000) ? 11.200 : 11.508;
564 2 23 return (n < NPRIMES_SMALL) ? primes_small[n] : inverse_R(n);
575 5917 1089 if (n < NPRIMES_SMALL)
580 0 1089 MPUassert(upper_limit > 0, "nth_prime got an upper limit of 0");
589 24 1065 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) {
593 1067 0 if (segment_size > 0)
614 3 19 if (count >= n) { /* Too far. Walk backwards */
615 0 3 if (is_prime(lower_limit)) count--;
616 4 3 for (p = 0; p <= (count-n); p++)
626 1067 19 if (count == target)
633 19 19 while (count < target) {
635 18 1 if ( (30*(segbase+segment_size)+29) > upper_limit )
644 0 19 if (count < target)
648 0 19 MPUassert(count == target, "nth_prime got incorrect count");
689 416 2 if (beg <= 3 && end >= 10000000) {
6 410 if (beg <= 3 && end >= 10000000) {
691 40 0 for (exp = 0; exp < twin_num_exponents && end >= base; exp++) {
34 6 for (exp = 0; exp < twin_num_exponents && end >= base; exp++) {
692 284 28 for (mult = 1; mult < 10 && end >= mult*base; mult++) {
278 6 for (mult = 1; mult < 10 && end >= mult*base; mult++) {
695 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;
700 410 8 if (beg <= 3 && end >= 3) sum++;
410 0 if (beg <= 3 && end >= 3) sum++;
701 410 8 if (beg <= 5 && end >= 5) sum++;
410 0 if (beg <= 5 && end >= 5) sum++;
702 410 8 if (beg < 11) beg = 7;
703 418 0 if (beg <= end) {
708 4974 418 while ((beg % 30) != 1) {
709 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++;
712 2861 403 while ((end % 30) != 29) {
713 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++;
714 15 2846 end -= 2; if (beg > end) break;
717 403 15 if (beg <= end) {
720 403 403 while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) {
725 53313 403 while (sp < spend) {
727 7513 45800 if (!(s & 0x0C)) sum++;
728 5920 47393 if (!(s & 0x30)) sum++;
729 18470 34843 if (!(s & 0x80) && !(*sp & 0x01)) sum++;
6819 11651 if (!(s & 0x80) && !(*sp & 0x01)) sum++;
732 148 255 if (!(s & 0x0C)) sum++;
733 100 303 if (!(s & 0x30)) sum++;
734 258 145 if (!(s & 0x80) && is_prime(seg_high+2)) sum++;
172 86 if (!(s & 0x80) && is_prime(seg_high+2)) sum++;
748 6 48 if (n < 6) {
763 48 0 if (dend < (double)end) end = (UV) dend;
766 0 48 if (n > 58980) { /* Use twin_prime_count tables to accelerate if possible */
768 0 0 for (exp = 0; exp < twin_num_exponents && end >= base; exp++) {
0 0 for (exp = 0; exp < twin_num_exponents && end >= base; exp++) {
769 0 0 for (mult = 1; mult < 10 && n > twin_steps[step]; mult++) {
0 0 for (mult = 1; mult < 10 && n > twin_steps[step]; mult++) {
772 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;
777 48 0 if (beg == 2) { beg = 31; n -= 5; }
782 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)) {
785 4428 0 for (p = 0; p < bytes; p++) {
787 4428 0 if (p+1 < bytes) s |= (((UV)segment[p+1]) << 8);
788 0 0 else if (!is_prime(seg_high+2)) s |= 0xFF00;
789 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; }
790 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; }
791 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; }
806 1 57 if (n < 6)
814 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) :
819 0 57 if (hi <= lo) hi = UV_MAX;
820 616 57 while (lo < hi) {
822 329 287 if (twin_prime_count_approx(mid) < fn) lo = mid+1;
900 0 0 New(0, V, r2+1, uint128_t);
901 0 0 New(0, S, r2+1, uint128_t);
902 0 0 for (k = 0; k <= r2; k++) {
903 0 0 uint128_t v = (k <= r) ? k : n/(r2-k+1);
908 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) {
910 0 0 for (j = k-1; j > 1 && V[j] >= p2; j--) {
0 0 for (j = k-1; j > 1 && V[j] >= p2; j--) {
912 0 0 if (a > r) a = r2 - n/a + 1;
913 0 0 if (b > r) b = r2 - n/b + 1;
930 1000 3 if ((low <= 2) && (high >= 2)) sum += 2;
1000 0 if ((low <= 2) && (high >= 2)) sum += 2;
931 1000 3 if ((low <= 3) && (high >= 3)) sum += 3;
999 1 if ((low <= 3) && (high >= 3)) sum += 3;
932 1000 3 if ((low <= 5) && (high >= 5)) sum += 5;
997 3 if ((low <= 5) && (high >= 5)) sum += 5;
933 1000 3 if (low < 7) low = 7;
937 1000 3 if (low == 7 && high >= 29505444491) return 0;
0 1000 if (low == 7 && high >= 29505444491) return 0;
938 0 1003 if (low >= 1e10 && (high-low) >= 32e9) return 0;
0 0 if (low >= 1e10 && (high-low) >= 32e9) return 0;
939 0 1003 if (low >= 1e13 && (high-low) >= 5e7) return 0;
0 0 if (low >= 1e13 && (high-low) >= 5e7) return 0;
945 1000 3 if (low == 7 && high >= 2e8) {
0 1000 if (low == 7 && high >= 2e8) {
947 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++) {
954 998 5 if (low <= high) {
958 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)) {
967 2005 0 for (i = 0; i < 8 && p+wheel30[i] < low; i++)
1007 998 for (i = 0; i < 8 && p+wheel30[i] < low; i++)
968 3 1004 if ( (*sp & (1<
972 7984 998 for (i = 0; i < 8; i++)
973 4908 3076 if ( (*spend & (1< high )
2459 2449 if ( (*spend & (1< high )
976 28641 998 while (sp <= spend) {
978 28641 0 if (sum < (UV_MAX >> 3) && pbase < (UV_MAX >> 5)) {
28641 0 if (sum < (UV_MAX >> 3) && pbase < (UV_MAX >> 5)) {
983 0 0 for (i = 0; i < byte_zeros[s]; i++) {
984 0 0 if (sum+pbase < sum) overflow = 1;
987 0 0 if (sum+byte_sum[s] < sum) overflow = 1;
989 0 0 if (overflow) break;
996 1003 0 if (!overflow && return_sum != 0) *return_sum = sum;
1003 0 if (!overflow && return_sum != 0) *return_sum = sum;