| line |
true |
false |
branch |
|
123
|
20 |
0 |
uint32 max_index = (n < 67) ? 18 |
|
|
20 |
0 |
uint32 max_index = (n < 67) ? 18 |
|
127
|
0 |
20 |
New(0, plist, max_index+1, uint32_t); |
|
130
|
20 |
0 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
60 |
8887 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
40 |
20 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
20 |
20 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
2306 |
6581 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
8 |
2307 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
9 |
2298 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
8 |
2298 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
0 |
8879 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
|
12 |
8927 |
START_DO_FOR_EACH_PRIME(2, n) { |
|
159
|
11072 |
140 |
for (i = 2, p = 3; p*p < start + (16*PREV_SIEVE_SIZE); p = primes[++i]) |
|
160
|
437 |
10635 |
for (j = (start == 0) ? p*p/2 : (p-1) - ((start+(p-1))/2) % p; |
|
|
860809 |
11072 |
for (j = (start == 0) ? p*p/2 : (p-1) - ((start+(p-1))/2) % p; |
|
169
|
0 |
90739 |
if (n <= 3) return (n == 3) ? 2 : 0; |
|
|
0 |
0 |
if (n <= 3) return (n == 3) ? 2 : 0; |
|
170
|
0 |
90739 |
if (n > sieve_max) croak("ps overflow\n"); |
|
179
|
140 |
90703 |
if (sieve_start != *segment_start) { /* Fill sieve if necessary */ |
|
184
|
90739 |
423505 |
if (sieve[bit_offset / 8] & (1u << (bit_offset % 8))) |
|
186
|
423401 |
104 |
} while (bit_offset-- > 0); |
|
217
|
33165 |
20 |
for (i = 1; i < tableSize; ++i) |
|
221
|
33165 |
20 |
for (i = 1; i < tableSize; ++i) { |
|
224
|
24694 |
8471 |
if (factor_table[i] != 65535) /* Already marked. */ |
|
226
|
8471 |
0 |
if (p < 65535) /* p is a small prime, so set the number. */ |
|
228
|
5215 |
3256 |
if (p >= max_prime) /* No multiples will be in the table */ |
|
233
|
57677 |
3256 |
for (factor = 3; factor < max_factor; factor += 2) { |
|
235
|
24694 |
32983 |
if (factor_table[index] == 65535) /* p is smallest factor */ |
|
237
|
25806 |
7177 |
else if (factor_table[index] > 0) /* Change number of factors */ |
|
242
|
6636 |
3256 |
for (factor = p; factor < max_factor; factor += 2*p) |
|
296
|
2745 |
554 |
if (a > c) { |
|
299
|
5877 |
152 |
for (i = c+1; i <= a; i++) { |
|
303
|
2593 |
3284 |
if (xp < p) { |
|
304
|
0 |
2593 |
while (x < pa) { |
|
323
|
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]; |
|
324
|
0 |
0 |
else if (a <= PHIC) return sign * tablephi(x, a); |
|
325
|
0 |
0 |
else if (x < primes[a+1]) sum = sign; |
|
329
|
0 |
0 |
UV a2, iters = (a*a > x) ? segment_prime_count(2,isqrt(x)) : a; |
|
331
|
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); |
|
333
|
0 |
0 |
for (a2 = c+1; a2 <= iters; a2++) |
|
336
|
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) |
|
343
|
2 |
3299 |
if (x <= PHIC) |
|
347
|
0 |
3299 |
if (a > (x >> 1)) return 1; |
|
350
|
0 |
3299 |
if (a > 203280221) { /* prime_count(2**32) */ |
|
352
|
0 |
0 |
return (a > pc) ? 1 : pc - a + 1; |
|
355
|
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 */ |
|
356
|
0 |
0 |
if ( LMO_prime_count(x) < a) return 1; |
|
363
|
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) ) { |
|
367
|
0 |
0 |
UV res, max_cache_a = (a >= PHICACHEA) ? PHICACHEA : a+1; |
|
368
|
0 |
0 |
Newz(0, cache, PHICACHEX * max_cache_a, uint16_t); |
|
405
|
3434614 |
3576 |
for (i = 0, bc = 0; i+7 < words; i += 8) { |
|
417
|
16962 |
3576 |
for (; i < words; i++) |
|
455
|
11323 |
3576 |
for ( ;index <= last_index; index++) { |
|
456
|
3139 |
8184 |
if (index >= s->first_prime && index <= s->last_prime) { |
|
|
3139 |
0 |
if (index >= s->first_prime && index <= s->last_prime) { |
|
458
|
3139 |
0 |
sieve_zero(sieve, b, word_count); |
|
460
|
5358 |
5965 |
if (index <= s->last_prime_to_remove) { |
|
462
|
5358 |
0 |
if (b < size) { |
|
467
|
348469 |
317367 |
sieve_case_zero(0, 3, b, p, size, mult, sieve, word_count); |
|
|
1054 |
664782 |
sieve_case_zero(0, 3, b, p, size, mult, sieve, word_count); |
|
468
|
353713 |
312007 |
sieve_case_zero(1, 2, b, p, size, mult, sieve, word_count); |
|
|
757 |
664963 |
sieve_case_zero(1, 2, b, p, size, mult, sieve, word_count); |
|
469
|
353317 |
312328 |
sieve_case_zero(2, 1, b, p, size, mult, sieve, word_count); |
|
|
383 |
665262 |
sieve_case_zero(2, 1, b, p, size, mult, sieve, word_count); |
|
470
|
353021 |
312745 |
sieve_case_zero(3, 2, b, p, size, mult, sieve, word_count); |
|
|
755 |
665011 |
sieve_case_zero(3, 2, b, p, size, mult, sieve, word_count); |
|
471
|
352397 |
313341 |
sieve_case_zero(4, 1, b, p, size, mult, sieve, word_count); |
|
|
352 |
665386 |
sieve_case_zero(4, 1, b, p, size, mult, sieve, word_count); |
|
472
|
348817 |
317005 |
sieve_case_zero(5, 2, b, p, size, mult, sieve, word_count); |
|
|
715 |
665107 |
sieve_case_zero(5, 2, b, p, size, mult, sieve, word_count); |
|
473
|
352966 |
312864 |
sieve_case_zero(6, 3, b, p, size, mult, sieve, word_count); |
|
|
1047 |
664783 |
sieve_case_zero(6, 3, b, p, size, mult, sieve, word_count); |
|
474
|
353338 |
312362 |
sieve_case_zero(7, 1, b, p, size, mult, sieve, word_count); |
|
|
295 |
665405 |
sieve_case_zero(7, 1, b, p, size, mult, sieve, word_count); |
|
486
|
332 |
112 |
while (from < to) { |
|
487
|
105 |
227 |
uint32 words = (2*from > to) ? to-from : from; |
|
502
|
20 |
8 |
if (segment_start == 0) { |
|
507
|
3239 |
28 |
while (s->last_prime < sieve_last) { |
|
509
|
0 |
3239 |
if (p >= segment_start + size) |
|
513
|
2274 |
0 |
while (s->last_prime_to_remove < sieve_last) { |
|
516
|
28 |
2246 |
if (p2 >= segment_start + size) |
|
524
|
28 |
0 |
if (start_prime_index >= 3) /* Remove multiples of 3. */ |
|
525
|
1792 |
28 |
for (i = 3/2; i < 3 * SWORD_BITS; i += 3) |
|
529
|
28 |
0 |
if (start_prime_index >= 3) /* Remove multiples of 5. */ |
|
530
|
5376 |
28 |
for (i = 5/2; i < 15 * SWORD_BITS; i += 5) |
|
534
|
28 |
0 |
if (start_prime_index >= 4) /* Remove multiples of 7. */ |
|
535
|
26880 |
28 |
for (i = 7/2; i < 105 * SWORD_BITS; i += 7) |
|
539
|
28 |
0 |
if (start_prime_index >= 5) /* Remove multiples of 11. */ |
|
540
|
188160 |
28 |
for (i = 11/2; i < 1155 * SWORD_BITS; i += 11) |
|
547
|
20 |
8 |
if (size % SWORD_BITS) |
|
552
|
159451 |
28 |
for (i = 0; i < words; i++) |
|
580
|
20 |
79 |
if (n < SIEVE_LIMIT || n < 10000) return segment_prime_count(2, n); |
|
|
0 |
20 |
if (n < SIEVE_LIMIT || n < 10000) return segment_prime_count(2, n); |
|
589
|
7 |
13 |
M = (N3 > 500) ? M_FACTOR(N3) : N3+N3/2; |
|
590
|
0 |
20 |
if (M >= N2) M = N2 - 1; /* M must be smaller than N^1/2 */ |
|
591
|
0 |
20 |
if (M < N3) M = N3; /* M must be at least N^1/3 */ |
|
601
|
0 |
20 |
New(0, ss.totals, K3+2, UV); |
|
602
|
0 |
20 |
New(0, ss.prime_index, K3+2, uint32); |
|
603
|
0 |
20 |
New(0, ss.first_bit_index, K3+2, uint32); |
|
606
|
20 |
0 |
if (ss.sieve == 0 || ss.word_count == 0 || ss.word_count_sum == 0 || |
|
|
20 |
0 |
if (ss.sieve == 0 || ss.word_count == 0 || ss.word_count_sum == 0 || |
|
|
20 |
0 |
if (ss.sieve == 0 || ss.word_count == 0 || ss.word_count_sum == 0 || |
|
|
20 |
0 |
if (ss.sieve == 0 || ss.word_count == 0 || ss.word_count_sum == 0 || |
|
607
|
20 |
0 |
ss.totals == 0 || ss.prime_index == 0 || ss.first_bit_index == 0 || |
|
|
20 |
0 |
ss.totals == 0 || ss.prime_index == 0 || ss.first_bit_index == 0 || |
|
|
0 |
20 |
ss.totals == 0 || ss.prime_index == 0 || ss.first_bit_index == 0 || |
|
619
|
11 |
20 |
for (j = (M+1)/2; factor_table[j] <= primes[c]; j++) /* */; |
|
625
|
0 |
20 |
if (piM < c) croak("N too small for LMO\n"); |
|
629
|
120 |
20 |
for (KM = c; primes[KM+1] * primes[KM+2] <= M && KM < piM; KM++) /* */; |
|
|
120 |
0 |
for (KM = c; primes[KM+1] * primes[KM+2] <= M && KM < piM; KM++) /* */; |
|
630
|
0 |
20 |
if (K3 < KM) K3 = KM; /* Ensure K3 >= KM */ |
|
638
|
20 |
0 |
prime = prev_sieve_prime( (N2 >= ps_start) ? ps_start : N2+1 ); |
|
644
|
29816 |
20 |
for (j = 0; j < end; j++) { |
|
646
|
11215 |
18601 |
if (lpf > primes[c]) { |
|
648
|
7538 |
3677 |
if (lpf & 0x01) sum2 += phi_value; else sum1 += phi_value; |
|
654
|
20 |
0 |
if (c < piM) { |
|
656
|
28065 |
20 |
for (j = (1+M/pc_1)/2; j < end; j++) { |
|
658
|
9971 |
18094 |
if (lpf > pc_1) { |
|
660
|
6916 |
3055 |
if (lpf & 0x01) sum1 += phi_value; else sum2 += phi_value; |
|
665
|
3259 |
20 |
for (k = 0; k <= K3; k++) ss.totals[k] = 0; |
|
666
|
240 |
20 |
for (k = 0; k < KM; k++) ss.prime_index[k] = end; |
|
672
|
2999 |
20 |
for (k = KM; k < K3; k++) { |
|
674
|
7290 |
14 |
while (last_prime > k+1 && pk * pk * primes[last_prime] > n) |
|
|
4305 |
2985 |
while (last_prime > k+1 && pk * pk * primes[last_prime] > n) |
|
681
|
28 |
20 |
for (sieve_start = 0; sieve_start < last_phi_sieve; sieve_start = sieve_end) { |
|
692
|
380 |
28 |
for (k = c+1; k < KM; k++) { |
|
694
|
380 |
0 |
uint32 start = (least_divisor >= pk * U32_CONST(0xFFFFFFFE)) |
|
698
|
684787 |
380 |
for (j = ss.prime_index[k] - 1; j >= start; j--) { |
|
700
|
171458 |
513329 |
if (lpf > pk) { |
|
702
|
148914 |
22544 |
if (lpf & 0x01) sum1 += phi_value; else sum2 += phi_value; |
|
705
|
363 |
17 |
if (start < ss.prime_index[k]) |
|
710
|
3140 |
28 |
for (; k < step7_max; k++) { |
|
713
|
3126 |
14 |
if (j >= k+2) { |
|
716
|
334635 |
0 |
while (endj > 7 && endj-7 >= k+2 && pk*primes[endj-7] > least_divisor) endj -= 8; |
|
|
331641 |
2994 |
while (endj > 7 && endj-7 >= k+2 && pk*primes[endj-7] > least_divisor) endj -= 8; |
|
|
331509 |
132 |
while (endj > 7 && endj-7 >= k+2 && pk*primes[endj-7] > least_divisor) endj -= 8; |
|
717
|
11112 |
2985 |
while ( endj >= k+2 && pk*primes[endj ] > least_divisor) endj--; |
|
|
10971 |
141 |
while ( endj >= k+2 && pk*primes[endj ] > least_divisor) endj--; |
|
719
|
2663043 |
3126 |
for ( ; j > endj; j--) |
|
725
|
3006 |
21 |
while (step7_max > KM && ss.prime_index[step7_max-1] < (step7_max-1)+2) |
|
|
2999 |
7 |
while (step7_max > KM && ss.prime_index[step7_max-1] < (step7_max-1)+2) |
|
731
|
90719 |
28 |
while (prime > least_divisor && prime_index >= piM) { |
|
|
90719 |
0 |
while (prime > least_divisor && prime_index >= piM) { |