| line |
true |
false |
branch |
|
122
|
847 |
0 |
uint32 max_index = (n < 67) ? 18 |
|
|
847 |
0 |
uint32 max_index = (n < 67) ? 18 |
|
126
|
0 |
847 |
New(0, plist, max_index+1, uint32_t); |
|
129
|
847 |
0 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
2541 |
235336 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
1694 |
847 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
847 |
847 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
52350 |
182986 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
193 |
52171 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
14 |
52157 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
193 |
52157 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
0 |
235143 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
654 |
237030 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
158
|
92375 |
2571 |
for (i = 2, p = 3; p*p < start + (16*PREV_SIEVE_SIZE); p = primes[++i]) |
|
159
|
19228 |
73147 |
for (j = (start == 0) ? p*p/2 : (p-1) - ((start+(p-1))/2) % p; |
|
|
14085639 |
92375 |
for (j = (start == 0) ? p*p/2 : (p-1) - ((start+(p-1))/2) % p; |
|
168
|
0 |
1671328 |
if (n <= 3) return (n == 3) ? 2 : 0; |
|
|
0 |
0 |
if (n <= 3) return (n == 3) ? 2 : 0; |
|
169
|
0 |
1671328 |
if (n > sieve_max) croak("ps overflow\n"); |
|
178
|
2571 |
1670355 |
if (sieve_start != *segment_start) { /* Fill sieve if necessary */ |
|
183
|
1671328 |
6223493 |
if (sieve[bit_offset / 8] & (1u << (bit_offset % 8))) |
|
185
|
6221895 |
1598 |
} while (bit_offset-- > 0); |
|
216
|
719531 |
847 |
for (i = 1; i < tableSize; ++i) |
|
220
|
719531 |
847 |
for (i = 1; i < tableSize; ++i) { |
|
223
|
502159 |
217372 |
if (factor_table[i] != 65535) /* Already marked. */ |
|
225
|
217372 |
0 |
if (p < 65535) /* p is a small prime, so set the number. */ |
|
227
|
132060 |
85312 |
if (p >= max_prime) /* No multiples will be in the table */ |
|
232
|
1104425 |
85312 |
for (factor = 3; factor < max_factor; factor += 2) { |
|
234
|
502159 |
602266 |
if (factor_table[index] == 65535) /* p is smallest factor */ |
|
236
|
476142 |
126124 |
else if (factor_table[index] > 0) /* Change number of factors */ |
|
241
|
142917 |
85312 |
for (factor = p; factor < max_factor; factor += 2*p) |
|
295
|
2745 |
554 |
if (a > c) { |
|
298
|
5877 |
152 |
for (i = c+1; i <= a; i++) { |
|
302
|
2593 |
3284 |
if (xp < p) { |
|
303
|
0 |
2593 |
while (x < pa) { |
|
322
|
0 |
0 |
if (PHICACHE_EXISTS(x,a)) return sign * cache[a*PHICACHEX+x]; |
|
|
0 |
0 |
if (PHICACHE_EXISTS(x,a)) return sign * cache[a*PHICACHEX+x]; |
|
|
0 |
0 |
if (PHICACHE_EXISTS(x,a)) return sign * cache[a*PHICACHEX+x]; |
|
323
|
0 |
0 |
else if (a <= PHIC) return sign * tablephi(x, a); |
|
324
|
0 |
0 |
else if (x < primes[a+1]) sum = sign; |
|
328
|
0 |
0 |
UV a2, iters = (a*a > x) ? segment_prime_count(2,isqrt(x)) : a; |
|
330
|
0 |
0 |
IV phixc = PHICACHE_EXISTS(x,c) ? cache[a*PHICACHEX+x] : tablephi(x,c); |
|
|
0 |
0 |
IV phixc = PHICACHE_EXISTS(x,c) ? cache[a*PHICACHEX+x] : tablephi(x,c); |
|
|
0 |
0 |
IV phixc = PHICACHE_EXISTS(x,c) ? cache[a*PHICACHEX+x] : tablephi(x,c); |
|
332
|
0 |
0 |
for (a2 = c+1; a2 <= iters; a2++) |
|
335
|
0 |
0 |
if (x < PHICACHEX && a < PHICACHEA && sign*sum <= SHRT_MAX) |
|
|
0 |
0 |
if (x < PHICACHEX && a < PHICACHEA && sign*sum <= SHRT_MAX) |
|
|
0 |
0 |
if (x < PHICACHEX && a < PHICACHEA && sign*sum <= SHRT_MAX) |
|
342
|
2 |
3299 |
if (x <= PHIC) |
|
346
|
0 |
3299 |
if (a > (x >> 1)) return 1; |
|
349
|
0 |
3299 |
if (a > 203280221) { /* prime_count(2**32) */ |
|
351
|
0 |
0 |
return (a > pc) ? 1 : pc - a + 1; |
|
354
|
0 |
3299 |
if (a > 1000000 && x < a*21) { /* x always less than 2^32 */ |
|
|
0 |
0 |
if (a > 1000000 && x < a*21) { /* x always less than 2^32 */ |
|
355
|
0 |
0 |
if ( LMO_prime_count(x) < a) return 1; |
|
362
|
3299 |
0 |
if ( a > 254 || (x > 1000000000 && a > 30) ) { |
|
|
0 |
3299 |
if ( a > 254 || (x > 1000000000 && a > 30) ) { |
|
|
0 |
0 |
if ( a > 254 || (x > 1000000000 && a > 30) ) { |
|
366
|
0 |
0 |
UV res, max_cache_a = (a >= PHICACHEA) ? PHICACHEA : a+1; |
|
367
|
0 |
0 |
Newz(0, cache, PHICACHEX * max_cache_a, uint16_t); |
|
404
|
40370817 |
97443 |
for (i = 0, bc = 0; i+7 < words; i += 8) { |
|
416
|
367791 |
97443 |
for (; i < words; i++) |
|
454
|
110414 |
97443 |
for ( ;index <= last_index; index++) { |
|
455
|
96696 |
13718 |
if (index >= s->first_prime && index <= s->last_prime) { |
|
|
96696 |
0 |
if (index >= s->first_prime && index <= s->last_prime) { |
|
457
|
96696 |
0 |
sieve_zero(sieve, b, word_count); |
|
459
|
78980 |
31434 |
if (index <= s->last_prime_to_remove) { |
|
461
|
78980 |
0 |
if (b < size) { |
|
466
|
3798347 |
2878996 |
sieve_case_zero(0, 3, b, p, size, mult, sieve, word_count); |
|
|
15535 |
6661808 |
sieve_case_zero(0, 3, b, p, size, mult, sieve, word_count); |
|
467
|
3927036 |
2745417 |
sieve_case_zero(1, 2, b, p, size, mult, sieve, word_count); |
|
|
10898 |
6661555 |
sieve_case_zero(1, 2, b, p, size, mult, sieve, word_count); |
|
468
|
3911095 |
2760246 |
sieve_case_zero(2, 1, b, p, size, mult, sieve, word_count); |
|
|
5190 |
6666151 |
sieve_case_zero(2, 1, b, p, size, mult, sieve, word_count); |
|
469
|
3897926 |
2778506 |
sieve_case_zero(3, 2, b, p, size, mult, sieve, word_count); |
|
|
10580 |
6665852 |
sieve_case_zero(3, 2, b, p, size, mult, sieve, word_count); |
|
470
|
3895538 |
2780755 |
sieve_case_zero(4, 1, b, p, size, mult, sieve, word_count); |
|
|
5294 |
6670999 |
sieve_case_zero(4, 1, b, p, size, mult, sieve, word_count); |
|
471
|
3811352 |
2868174 |
sieve_case_zero(5, 2, b, p, size, mult, sieve, word_count); |
|
|
10568 |
6668958 |
sieve_case_zero(5, 2, b, p, size, mult, sieve, word_count); |
|
472
|
3915790 |
2763536 |
sieve_case_zero(6, 3, b, p, size, mult, sieve, word_count); |
|
|
15724 |
6663602 |
sieve_case_zero(6, 3, b, p, size, mult, sieve, word_count); |
|
473
|
3918671 |
2755245 |
sieve_case_zero(7, 1, b, p, size, mult, sieve, word_count); |
|
|
5191 |
6668725 |
sieve_case_zero(7, 1, b, p, size, mult, sieve, word_count); |
|
485
|
9562 |
3468 |
while (from < to) { |
|
486
|
3194 |
6368 |
uint32 words = (2*from > to) ? to-from : from; |
|
501
|
847 |
20 |
if (segment_start == 0) { |
|
506
|
100931 |
867 |
while (s->last_prime < sieve_last) { |
|
508
|
0 |
100931 |
if (p >= segment_start + size) |
|
512
|
78126 |
0 |
while (s->last_prime_to_remove < sieve_last) { |
|
515
|
867 |
77259 |
if (p2 >= segment_start + size) |
|
523
|
867 |
0 |
if (start_prime_index >= 3) /* Remove multiples of 3. */ |
|
524
|
55488 |
867 |
for (i = 3/2; i < 3 * SWORD_BITS; i += 3) |
|
528
|
867 |
0 |
if (start_prime_index >= 3) /* Remove multiples of 5. */ |
|
529
|
166464 |
867 |
for (i = 5/2; i < 15 * SWORD_BITS; i += 5) |
|
533
|
867 |
0 |
if (start_prime_index >= 4) /* Remove multiples of 7. */ |
|
534
|
832320 |
867 |
for (i = 7/2; i < 105 * SWORD_BITS; i += 7) |
|
538
|
867 |
0 |
if (start_prime_index >= 5) /* Remove multiples of 11. */ |
|
539
|
5826240 |
867 |
for (i = 11/2; i < 1155 * SWORD_BITS; i += 11) |
|
546
|
829 |
38 |
if (size % SWORD_BITS) |
|
551
|
1955904 |
867 |
for (i = 0; i < words; i++) |
|
579
|
847 |
51613 |
if (n < _MPU_LMO_CROSSOVER || n < 10000) return segment_prime_count(2, n); |
|
|
0 |
847 |
if (n < _MPU_LMO_CROSSOVER || n < 10000) return segment_prime_count(2, n); |
|
600
|
488 |
359 |
M = (N3 > 500) ? M_FACTOR(N3) : N3+N3/2; |
|
601
|
0 |
847 |
if (M >= N2) M = N2 - 1; /* M must be smaller than N^1/2 */ |
|
602
|
0 |
847 |
if (M < N3) M = N3; /* M must be at least N^1/3 */ |
|
612
|
0 |
847 |
New(0, ss.totals, K3+2, UV); |
|
613
|
0 |
847 |
New(0, ss.prime_index, K3+2, uint32); |
|
614
|
0 |
847 |
New(0, ss.first_bit_index, K3+2, uint32); |
|
617
|
847 |
0 |
if (ss.sieve == 0 || ss.word_count == 0 || ss.word_count_sum == 0 || |
|
|
847 |
0 |
if (ss.sieve == 0 || ss.word_count == 0 || ss.word_count_sum == 0 || |
|
|
847 |
0 |
if (ss.sieve == 0 || ss.word_count == 0 || ss.word_count_sum == 0 || |
|
|
847 |
0 |
if (ss.sieve == 0 || ss.word_count == 0 || ss.word_count_sum == 0 || |
|
618
|
847 |
0 |
ss.totals == 0 || ss.prime_index == 0 || ss.first_bit_index == 0 || |
|
|
847 |
0 |
ss.totals == 0 || ss.prime_index == 0 || ss.first_bit_index == 0 || |
|
|
0 |
847 |
ss.totals == 0 || ss.prime_index == 0 || ss.first_bit_index == 0 || |
|
630
|
945 |
847 |
for (j = (M+1)/2; factor_table[j] <= primes[c]; j++) /* */; |
|
636
|
0 |
847 |
if (piM < c) croak("N too small for LMO\n"); |
|
640
|
3798 |
847 |
for (KM = c; primes[KM+1] * primes[KM+2] <= M && KM < piM; KM++) /* */; |
|
|
3798 |
0 |
for (KM = c; primes[KM+1] * primes[KM+2] <= M && KM < piM; KM++) /* */; |
|
641
|
0 |
847 |
if (K3 < KM) K3 = KM; /* Ensure K3 >= KM */ |
|
649
|
847 |
0 |
prime = prev_sieve_prime( (N2 >= ps_start) ? ps_start : N2+1 ); |
|
655
|
578180 |
847 |
for (j = 0; j < end; j++) { |
|
657
|
216352 |
361828 |
if (lpf > primes[c]) { |
|
659
|
173817 |
42535 |
if (lpf & 0x01) sum2 += phi_value; else sum1 += phi_value; |
|
665
|
847 |
0 |
if (c < piM) { |
|
667
|
544192 |
847 |
for (j = (1+M/pc_1)/2; j < end; j++) { |
|
669
|
191646 |
352546 |
if (lpf > pc_1) { |
|
671
|
161464 |
30182 |
if (lpf & 0x01) sum1 += phi_value; else sum2 += phi_value; |
|
676
|
101778 |
847 |
for (k = 0; k <= K3; k++) ss.totals[k] = 0; |
|
677
|
8880 |
847 |
for (k = 0; k < KM; k++) ss.prime_index[k] = end; |
|
683
|
92051 |
847 |
for (k = KM; k < K3; k++) { |
|
685
|
168446 |
275 |
while (last_prime > k+1 && pk * pk * primes[last_prime] > n) |
|
|
76670 |
91776 |
while (last_prime > k+1 && pk * pk * primes[last_prime] > n) |
|
692
|
867 |
847 |
for (sieve_start = 0; sieve_start < last_phi_sieve; sieve_start = sieve_end) { |
|
703
|
3463 |
867 |
for (k = c+1; k < KM; k++) { |
|
705
|
3463 |
0 |
uint32 start = (least_divisor >= pk * U32_CONST(0xFFFFFFFE)) |
|
709
|
4140185 |
3463 |
for (j = ss.prime_index[k] - 1; j >= start; j--) { |
|
711
|
1186073 |
2954112 |
if (lpf > pk) { |
|
713
|
1095902 |
90171 |
if (lpf & 0x01) sum1 += phi_value; else sum2 += phi_value; |
|
716
|
3446 |
17 |
if (start < ss.prime_index[k]) |
|
721
|
92246 |
867 |
for (; k < step7_max; k++) { |
|
724
|
91971 |
275 |
if (j >= k+2) { |
|
727
|
2409155 |
0 |
while (endj > 7 && endj-7 >= k+2 && pk*primes[endj-7] > least_divisor) endj -= 8; |
|
|
2317357 |
91798 |
while (endj > 7 && endj-7 >= k+2 && pk*primes[endj-7] > least_divisor) endj -= 8; |
|
|
2317184 |
173 |
while (endj > 7 && endj-7 >= k+2 && pk*primes[endj-7] > least_divisor) endj -= 8; |
|
728
|
322077 |
91776 |
while ( endj >= k+2 && pk*primes[endj ] > least_divisor) endj--; |
|
|
321882 |
195 |
while ( endj >= k+2 && pk*primes[endj ] > least_divisor) endj--; |
|
730
|
18859354 |
91971 |
for ( ; j > endj; j--) |
|
736
|
92070 |
848 |
while (step7_max > KM && ss.prime_index[step7_max-1] < (step7_max-1)+2) |
|
|
92051 |
19 |
while (step7_max > KM && ss.prime_index[step7_max-1] < (step7_max-1)+2) |
|
742
|
1670481 |
867 |
while (prime > least_divisor && prime_index >= piM) { |
|
|
1670481 |
0 |
while (prime > least_divisor && prime_index >= piM) { |