| line |
true |
false |
branch |
|
41
|
0 |
32 |
if (nc > NSMALLPRIMES) return 1; /* TODO */ |
|
42
|
211 |
30 |
for (i = 0; i < nc; i++) { |
|
45
|
1695 |
211 |
for (c = 0; c < nc; c++) |
|
47
|
674 |
2 |
for (j = 0; j < p; j++) |
|
48
|
209 |
465 |
if (rset[j] == 0) |
|
50
|
2 |
209 |
if (j == p) /* All values were 1 */ |
|
59
|
141 |
12 |
for (c = 1; c < nc; c++) |
|
60
|
76 |
65 |
if (!is_prob_prime(p+cl[c])) |
|
70
|
0 |
32 |
INIT_VLIST(retlist); |
|
71
|
12 |
20 |
if (beg <= 2 && end >= 2 && is_cluster(2, nc, cl)) PUSH_VLIST(retlist, 2); |
|
|
12 |
0 |
if (beg <= 2 && end >= 2 && is_cluster(2, nc, cl)) PUSH_VLIST(retlist, 2); |
|
|
0 |
12 |
if (beg <= 2 && end >= 2 && is_cluster(2, nc, cl)) PUSH_VLIST(retlist, 2); |
|
|
0 |
0 |
if (beg <= 2 && end >= 2 && is_cluster(2, nc, cl)) PUSH_VLIST(retlist, 2); |
|
|
0 |
0 |
if (beg <= 2 && end >= 2 && is_cluster(2, nc, cl)) PUSH_VLIST(retlist, 2); |
|
72
|
12 |
20 |
if (beg <= 3 && end >= 3 && is_cluster(3, nc, cl)) PUSH_VLIST(retlist, 3); |
|
|
12 |
0 |
if (beg <= 3 && end >= 3 && is_cluster(3, nc, cl)) PUSH_VLIST(retlist, 3); |
|
|
4 |
8 |
if (beg <= 3 && end >= 3 && is_cluster(3, nc, cl)) PUSH_VLIST(retlist, 3); |
|
|
0 |
4 |
if (beg <= 3 && end >= 3 && is_cluster(3, nc, cl)) PUSH_VLIST(retlist, 3); |
|
|
0 |
0 |
if (beg <= 3 && end >= 3 && is_cluster(3, nc, cl)) PUSH_VLIST(retlist, 3); |
|
73
|
12 |
20 |
if (beg <= 5 && end >= 5 && is_cluster(5, nc, cl)) PUSH_VLIST(retlist, 5); |
|
|
12 |
0 |
if (beg <= 5 && end >= 5 && is_cluster(5, nc, cl)) PUSH_VLIST(retlist, 5); |
|
|
6 |
6 |
if (beg <= 5 && end >= 5 && is_cluster(5, nc, cl)) PUSH_VLIST(retlist, 5); |
|
|
0 |
6 |
if (beg <= 5 && end >= 5 && is_cluster(5, nc, cl)) PUSH_VLIST(retlist, 5); |
|
|
0 |
0 |
if (beg <= 5 && end >= 5 && is_cluster(5, nc, cl)) PUSH_VLIST(retlist, 5); |
|
74
|
12 |
20 |
if (beg < 7) beg = 7; |
|
77
|
2 |
30 |
if (!is_admissible(nc, cl) && end > sprimes[nc]) |
|
|
2 |
0 |
if (!is_admissible(nc, cl) && end > sprimes[nc]) |
|
80
|
32 |
0 |
if (beg <= end) { |
|
86
|
35 |
32 |
while (next_segment_primes(ctx, &seg_base, &seg_beg, &seg_end)) { |
|
87
|
34 |
1 |
UV sp, last_sieve_cluster = (seg_end >= cl[nc-1]) ? seg_end-cl[nc-1] : 0; |
|
88
|
259677 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_beg, seg_end ) |
|
|
32 |
259645 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_beg, seg_end ) |
|
|
259643 |
2 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_beg, seg_end ) |
|
|
259677 |
13931 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_beg, seg_end ) |
|
|
13963 |
35 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_beg, seg_end ) |
|
89
|
259591 |
52 |
if (p <= last_sieve_cluster) { |
|
91
|
277909 |
12005 |
for (c = 1; c < nc; c++) |
|
92
|
247586 |
30323 |
if (!is_prime_in_sieve(segment, sp+cl[c])) |
|
94
|
12005 |
247586 |
if (c == nc) |
|
95
|
60 |
11945 |
PUSH_VLIST(retlist,p); |
|
|
0 |
60 |
PUSH_VLIST(retlist,p); |
|
97
|
2 |
50 |
if (is_cluster(p, nc, cl)) |
|
98
|
0 |
2 |
PUSH_VLIST(retlist, p); |
|
|
0 |
0 |
PUSH_VLIST(retlist, p); |
|
125
|
0 |
32 |
if ((UV_MAX - cl[nc-1]) < high) return 0; /* Overflow */ |
|
127
|
11 |
21 |
if ( ((high-low) < 10000) |
|
128
|
3 |
8 |
|| (nc == 3 && ((high>>31) >> 16) == 0) /* sieving large vals is slow */ |
|
|
0 |
3 |
|| (nc == 3 && ((high>>31) >> 16) == 0) /* sieving large vals is slow */ |
|
129
|
1 |
7 |
|| (nc == 2 && ((high>>31) >> 27) == 0) |
|
|
0 |
1 |
|| (nc == 2 && ((high>>31) >> 27) == 0) |
|
130
|
0 |
7 |
|| (nc < 2) ) |
|
133
|
6 |
1 |
if (!(low&1)) low++; |
|
134
|
7 |
0 |
if (!(high&1)) high--; |
|
136
|
0 |
7 |
INIT_VLIST(retlist); |
|
138
|
7 |
0 |
if (low < lastspr) { |
|
141
|
15 |
7 |
for (i = 0; i < t; i++) |
|
142
|
0 |
15 |
PUSH_VLIST(retlist, s[i]); |
|
|
0 |
0 |
PUSH_VLIST(retlist, s[i]); |
|
146
|
0 |
7 |
if (low > high) { |
|
150
|
7 |
0 |
if (low&1) low--; |
|
157
|
21 |
7 |
for (pi = 2, ppr = 1, i = 0; i <= pi; i++) ppr *= sprimes[i]; |
|
160
|
105 |
7 |
for (i = 1; i <= ppr; i += 2) { |
|
161
|
210 |
6 |
for (c = 0; c < nc; c++) { |
|
163
|
99 |
111 |
if (gcd_ui(v, ppr) != 1) break; |
|
165
|
6 |
99 |
if (c == nc) |
|
166
|
0 |
6 |
ADDVAL32(residues, nres, allocres, i); |
|
|
0 |
0 |
ADDVAL32(residues, nres, allocres, i); |
|
172
|
31 |
0 |
while (pi++ < 12) { |
|
178
|
30 |
1 |
if (nres == 0 || nres > targres/(p/2) || newppr > maxppr) break; |
|
|
30 |
0 |
if (nres == 0 || nres > targres/(p/2) || newppr > maxppr) break; |
|
|
24 |
6 |
if (nres == 0 || nres > targres/(p/2) || newppr > maxppr) break; |
|
179
|
0 |
24 |
if (_verbose > 1) printf("cluster sieve found %"UVuf" residues mod %"UVuf"\n", nres, ppr); |
|
182
|
288 |
24 |
for (i = 0; i < p; i++) { |
|
183
|
8794 |
288 |
for (j = 0; j < nres; j++) { |
|
185
|
37642 |
6158 |
for (c = 0; c < nc; c++) { |
|
187
|
2636 |
35006 |
if ((v % p) == 0) break; |
|
189
|
6158 |
2636 |
if (c == nc) |
|
190
|
4 |
6154 |
ADDVAL32(res2, nres2, allocres2, r); |
|
|
0 |
4 |
ADDVAL32(res2, nres2, allocres2, r); |
|
199
|
0 |
7 |
if (_verbose) printf("cluster sieve using %"UVuf" residues mod %"UVuf"\n", nres, ppr); |
|
202
|
1 |
6 |
if (nres == 0) { |
|
218
|
114 |
6 |
for (i = 0; i < p1; i++) { crem_0[i*p1]=0; crem_0[i*p2]=0; } |
|
219
|
24 |
6 |
for ( ; i < p2; i++) { crem_0[i*p1]=0; } |
|
220
|
174 |
6 |
for (i = 0; i < p3; i++) { crem_1[i*p3]=0; crem_1[i*p4]=0; } |
|
221
|
12 |
6 |
for ( ; i < p4; i++) { crem_1[i*p3]=0; } |
|
222
|
222 |
6 |
for (i = 0; i < p5; i++) { crem_2[i*p5]=0; crem_2[i*p6]=0; } |
|
223
|
24 |
6 |
for ( ; i < p6; i++) { crem_2[i*p5]=0; } |
|
224
|
28 |
6 |
for (c = 1; c < nc; c++) { |
|
226
|
2 |
26 |
if (c1 >= p1) c1 %= p1; |
|
227
|
0 |
28 |
if (c2 >= p2) c2 %= p2; |
|
228
|
532 |
28 |
for (i = 1; i <= p1; i++) { crem_0[i*p1-c1]=0; crem_0[i*p2-c2]=0; } |
|
229
|
112 |
28 |
for ( ; i <= p2; i++) { crem_0[i*p1-c1]=0; } |
|
230
|
0 |
28 |
if (c3 >= p3) c3 %= p3; |
|
231
|
0 |
28 |
if (c4 >= p4) c4 %= p4; |
|
232
|
812 |
28 |
for (i = 1; i <= p3; i++) { crem_1[i*p3-c3]=0; crem_1[i*p4-c4]=0; } |
|
233
|
56 |
28 |
for ( ; i <= p4; i++) { crem_1[i*p3-c3]=0; } |
|
234
|
0 |
28 |
if (c5 >= p5) c5 %= p5; |
|
235
|
0 |
28 |
if (c6 >= p6) c6 %= p6; |
|
236
|
1036 |
28 |
for (i = 1; i <= p5; i++) { crem_2[i*p5-c5]=0; crem_2[i*p6-c6]=0; } |
|
237
|
112 |
28 |
for ( ; i <= p6; i++) { crem_2[i*p5-c5]=0; } |
|
239
|
0 |
6 |
New(0, resmod_0, nres, uint32_t); |
|
240
|
0 |
6 |
New(0, resmod_1, nres, uint32_t); |
|
241
|
0 |
6 |
New(0, resmod_2, nres, uint32_t); |
|
242
|
5626 |
6 |
for (i = 0; i < nres; i++) { |
|
250
|
0 |
6 |
New(0, VPrem, maxpi, char*); |
|
252
|
822 |
6 |
for (pi = startpi+6; pi < maxpi; pi++) { |
|
257
|
822 |
6 |
for (pi = startpi+6, smallnc = 0; pi < maxpi; pi++) { |
|
261
|
34 |
822 |
while (smallnc < nc && cl[smallnc] < p) smallnc++; |
|
|
34 |
0 |
while (smallnc < nc && cl[smallnc] < p) smallnc++; |
|
262
|
3836 |
822 |
for (c = 1; c < smallnc; c++) prem[p-cl[c]] = 0; |
|
263
|
0 |
822 |
for ( ; c < nc; c++) prem[p-(cl[c]%p)] = 0; |
|
266
|
0 |
6 |
New(0, cres, nres, UV); |
|
273
|
18 |
6 |
while (low <= high) { |
|
279
|
16878 |
18 |
for (r = 0, ncres = 0; r < nres; r++) { |
|
280
|
8883 |
7995 |
addmodded(remr, rem_0, resmod_0[r], pp_0); |
|
281
|
9995 |
6883 |
if (crem_0[remr]) { |
|
282
|
8202 |
1793 |
addmodded(remr, rem_1, resmod_1[r], pp_1); |
|
283
|
7113 |
2882 |
if (crem_1[remr]) { |
|
284
|
3031 |
4082 |
addmodded(remr, rem_2, resmod_2[r], pp_2); |
|
285
|
5520 |
1593 |
if (crem_2[remr]) { |
|
291
|
6 |
12 |
addmodded(rem_0, rem_0, remadd_0, pp_0); |
|
292
|
18 |
0 |
addmodded(rem_1, rem_1, remadd_1, pp_1); |
|
293
|
12 |
6 |
addmodded(rem_2, rem_2, remadd_2, pp_2); |
|
297
|
2438 |
17 |
for (pi = startpi+6; pi < maxpi && ncres > 0; pi++) { |
|
|
2437 |
1 |
for (pi = startpi+6; pi < maxpi && ncres > 0; pi++) { |
|
303
|
2437 |
0 |
if (startpi <= 9) { /* Residues are 32-bit */ |
|
304
|
139797 |
2437 |
for (r = 0, nr = 0; r < ncres; r++) { |
|
305
|
134664 |
5133 |
if (prem[ (rem+(uint32_t)cres[r]) % p ]) |
|
309
|
0 |
0 |
for (r = 0, nr = 0; r < ncres; r++) { |
|
310
|
0 |
0 |
if (prem[ (rem+cres[r]) % p ]) |
|
316
|
0 |
18 |
if (_verbose > 2) printf("cluster sieve range has %u residues left\n", ncres); |
|
319
|
272 |
14 |
for (r = 0; r < ncres; r++) { |
|
321
|
4 |
268 |
if (p > high) break; |
|
323
|
1166 |
259 |
for (c = 0; c < nc; c++) |
|
324
|
9 |
1157 |
if (num_mr++,!is_euler_plumb_pseudoprime(p+cl[c])) |
|
326
|
9 |
259 |
if (c < nc) continue; |
|
327
|
1134 |
259 |
for (c = 0; c < nc; c++) |
|
328
|
0 |
1134 |
if (num_lucas++,!is_almost_extra_strong_lucas_pseudoprime(p+cl[c], 1)) |
|
330
|
0 |
259 |
if (c < nc) continue; |
|
331
|
1 |
258 |
PUSH_VLIST(retlist, p); |
|
|
0 |
1 |
PUSH_VLIST(retlist, p); |
|
334
|
0 |
18 |
if (low < ppr) low = UV_MAX; |
|
337
|
0 |
6 |
if (_verbose) printf("cluster sieve ran %"UVuf" MR and %"UVuf" Lucas tests\n", num_mr, num_lucas); |
|
338
|
822 |
6 |
for (pi = startpi+6; pi < maxpi; pi++) |