| line |
true |
false |
branch |
|
136
|
12253 |
429666 |
if (n <= 10) |
|
137
|
8443 |
3810 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
|
5315 |
3128 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
|
3227 |
2088 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
|
1817 |
1410 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
139
|
428000 |
1666 |
if (n < UVCONST(200000000)) { |
|
146
|
240106 |
187894 |
if (mtab == 0) |
|
150
|
17981 |
169913 |
if (d < NPRIME_SIEVE30) |
|
151
|
4073 |
13908 |
return (prime_sieve30[d] & mtab) ? 0 : 2; |
|
153
|
141017 |
28896 |
if (!(n%7) || !(n%11) || !(n%13)) return 0; |
|
|
127265 |
13752 |
if (!(n%7) || !(n%11) || !(n%13)) return 0; |
|
|
10410 |
116855 |
if (!(n%7) || !(n%11) || !(n%13)) return 0; |
|
156
|
105166 |
11689 |
if (n <= get_prime_cache(0,0)) { |
|
158
|
105166 |
0 |
if (n <= get_prime_cache(0, &sieve)) |
|
159
|
44441 |
60725 |
isprime = 2*((sieve[d] & mtab) == 0); |
|
161
|
105166 |
0 |
if (isprime >= 0) |
|
173
|
16225 |
6258 |
if (n < 30*NPRIME_SIEVE30) { |
|
175
|
16224 |
1 |
if (next != 0) return next; |
|
178
|
0 |
6259 |
if (n >= MPU_MAX_PRIME) return 0; /* Overflow */ |
|
180
|
4059 |
2200 |
if (n < get_prime_cache(0,0)) { |
|
183
|
4059 |
0 |
next = (n < sieve_size) ? next_prime_in_sieve(sieve, n, sieve_size) : 0; |
|
185
|
4059 |
0 |
if (next != 0) return next; |
|
192
|
7450 |
2200 |
} while (!is_prob_prime(n)); |
|
201
|
17604 |
8172 |
if (n < 30*NPRIME_SIEVE30) |
|
204
|
4007 |
4165 |
if (n < get_prime_cache(0,0)) { |
|
207
|
4007 |
0 |
prev = (n < sieve_size) ? prev_prime_in_sieve(sieve, n) : 0; |
|
209
|
4007 |
0 |
if (prev != 0) return prev; |
|
216
|
10108 |
4165 |
} while (!is_prob_prime(n)); |
|
230
|
0 |
0 |
} while ((val = t)); |
|
232
|
0 |
0 |
while (--s > ptr) { char c = *s; *s = *ptr; *ptr++ = c; } |
|
237
|
0 |
0 |
if (res == -1) croak("print_primes write error"); |
|
243
|
0 |
0 |
if ((low <= 2) && (high >= 2)) bend += my_sprint(bend,2); |
|
|
0 |
0 |
if ((low <= 2) && (high >= 2)) bend += my_sprint(bend,2); |
|
244
|
0 |
0 |
if ((low <= 3) && (high >= 3)) bend += my_sprint(bend,3); |
|
|
0 |
0 |
if ((low <= 3) && (high >= 3)) bend += my_sprint(bend,3); |
|
245
|
0 |
0 |
if ((low <= 5) && (high >= 5)) bend += my_sprint(bend,5); |
|
|
0 |
0 |
if ((low <= 5) && (high >= 5)) bend += my_sprint(bend,5); |
|
246
|
0 |
0 |
if (low < 7) low = 7; |
|
248
|
0 |
0 |
if (low <= high) { |
|
252
|
0 |
0 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
253
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
255
|
0 |
0 |
if (bend-buf > 8000) { bend = write_buf(fd, buf, bend); } |
|
260
|
0 |
0 |
if (bend > buf) { bend = write_buf(fd, buf, bend); } |
|
282
|
46 |
22 |
if (sqrtn*sqrtn != hi) sqrtn++; /* ceil sqrtn */ |
|
285
|
68 |
0 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
187 |
352 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
119 |
68 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
64 |
55 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
29 |
323 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
0 |
29 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
0 |
29 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
0 |
29 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
0 |
352 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
68 |
471 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
287
|
87 |
384 |
if (p > nextlog) { |
|
291
|
0 |
471 |
for (i = PGTLO(p, lo); i <= hi; i += p) |
|
|
0 |
0 |
for (i = PGTLO(p, lo); i <= hi; i += p) |
|
|
146989 |
471 |
for (i = PGTLO(p, lo); i <= hi; i += p) |
|
293
|
0 |
471 |
for (i = PGTLO(p2, lo); i <= hi; i += p2) |
|
|
0 |
0 |
for (i = PGTLO(p2, lo); i <= hi; i += p2) |
|
|
37762 |
471 |
for (i = PGTLO(p2, lo); i <= hi; i += p2) |
|
297
|
21 |
47 |
logp = log2floor(lo); |
|
299
|
84642 |
68 |
for (i = lo; i <= hi; i++) { |
|
301
|
414 |
84228 |
if (i >= nextlog) { logp++; nextlog *= 2; } /* logp is log(p)/log(2) */ |
|
302
|
33096 |
51546 |
if (a & 0x80) { a = 0; } |
|
303
|
12342 |
39204 |
else if (a >= logp) { a = 1 - 2*(a&1); } |
|
307
|
47 |
21 |
if (lo == 0) mu[0] = 0; |
|
318
|
0 |
8 |
if (hi < lo) croak("_totient_range error hi %"UVuf" < lo %"UVuf"\n", hi, lo); |
|
319
|
0 |
8 |
New(0, totients, hi-lo+1, UV); |
|
322
|
2 |
6 |
if (hi < 100 || (hi-lo) < 10 || hi/(hi-lo+1) > 1000) { |
|
|
2 |
0 |
if (hi < 100 || (hi-lo) < 10 || hi/(hi-lo+1) > 1000) { |
|
|
0 |
2 |
if (hi < 100 || (hi-lo) < 10 || hi/(hi-lo+1) > 1000) { |
|
323
|
35 |
6 |
for (i = lo; i <= hi; i++) |
|
329
|
1 |
1 |
if (lo == 0) { |
|
332
|
1 |
0 |
UV max_index = (hi < 67) ? 18 |
|
|
1 |
0 |
UV max_index = (hi < 67) ? 18 |
|
337
|
0 |
1 |
New(0, prime, max_index, UV); /* could use prime_count_upper(hi) */ |
|
339
|
119 |
1 |
for (i = 2; i <= hi/2; i++) { |
|
341
|
60 |
59 |
if ( !(i&1) ) { |
|
342
|
1 |
59 |
if (i == 2) { totients[2] = 1; prime[nprimes++] = 2; } |
|
345
|
29 |
30 |
if (totients[i] == 0) { |
|
349
|
167 |
0 |
for (j=0; j < nprimes && index <= hi; index = i*prime[++j]) { |
|
|
127 |
40 |
for (j=0; j < nprimes && index <= hi; index = i*prime[++j]) { |
|
350
|
19 |
108 |
if (i % prime[j] == 0) { |
|
361
|
60 |
1 |
for (i = ((hi/2) + 1) | 1; i <= hi; i += 2) |
|
362
|
22 |
38 |
if (totients[i] == 0) |
|
369
|
25 |
1 |
for (i = lo; i <= hi; i++) { |
|
371
|
12 |
13 |
if (i % 2 == 0) v -= v/2; |
|
372
|
8 |
17 |
if (i % 3 == 0) v -= v/3; |
|
373
|
5 |
20 |
if (i % 5 == 0) v -= v/5; |
|
378
|
1 |
1 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
379
|
133 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
1 |
132 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
132 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
133 |
3 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
4 |
1 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
380
|
2 |
130 |
for (i = P2GTLO(2*p,p,lo); i <= hi; i += p) |
|
|
128 |
2 |
for (i = P2GTLO(2*p,p,lo); i <= hi; i += p) |
|
|
31 |
132 |
for (i = P2GTLO(2*p,p,lo); i <= hi; i += p) |
|
387
|
13 |
1 |
for (i = lo | 1; i <= hi; i += 2) |
|
388
|
2 |
11 |
if (totients[i-lo] == i) |
|
390
|
0 |
1 |
if (lo <= 1) totients[1-lo] = 1; |
|
406
|
1 |
44 |
if (n <= 1) return n; |
|
409
|
32 |
12 |
if (maxmu < u) maxmu = u; |
|
411
|
0 |
44 |
New(0, M, maxmu+1, short); |
|
413
|
56530 |
44 |
for (j = 1; j <= maxmu; j++) |
|
416
|
56530 |
44 |
for (m = 1; m <= u; m++) { |
|
417
|
34416 |
22114 |
if (mu[m] != 0) { |
|
424
|
228923217 |
34416 |
for (nmk = 1; nmk <= last_nmk; nmk++, nmkm += m) { |
|
429
|
17157 |
17259 |
sum += (mu[m] > 0) ? -inner_sum : inner_sum; |
|
446
|
15193 |
84 |
if ((n <= 3) || (n == UV_MAX)) return 1; |
|
|
0 |
15193 |
if ((n <= 3) || (n == UV_MAX)) return 1; |
|
447
|
17 |
15176 |
if ((n & (n-1)) == 0) return ctz(n); /* powers of 2 */ |
|
|
17 |
0 |
if ((n & (n-1)) == 0) return ctz(n); /* powers of 2 */ |
|
448
|
244 |
14932 |
if (is_perfect_square(n)) return 2 * powerof(isqrt(n)); |
|
449
|
49 |
14883 |
if (is_perfect_cube(n)) return 3 * powerof(icbrt(n)); |
|
452
|
8316 |
6567 |
t = n & 511; if ((t*77855451) & (t*4598053) & 862) return 1; |
|
454
|
15 |
6552 |
if (is_perfect_fifth(n)) return 5 * powerof(rootof(n,5)); |
|
455
|
7 |
6545 |
if (is_perfect_seventh(n)) return 7 * powerof(rootof(n,7)); |
|
457
|
1934 |
4611 |
if (n > 177146 && n <= UVCONST(1977326743)) { |
|
|
1842 |
92 |
if (n > 177146 && n <= UVCONST(1977326743)) { |
|
467
|
81 |
6460 |
if (n >= UVCONST(8589934592)) { |
|
471
|
2 |
79 |
if ( (t = n %121, !((t*19706187) & (t*61524433) & 876897796)) && |
|
|
0 |
2 |
if ( (t = n %121, !((t*19706187) & (t*61524433) & 876897796)) && |
|
475
|
0 |
0 |
if (n == ipow(root,11)) return 11; |
|
477
|
17 |
64 |
if ( (t = n %131, !((t*1545928325) & (t*1355660813) & 2771533888U)) && |
|
|
2 |
15 |
if ( (t = n %131, !((t*1545928325) & (t*1355660813) & 2771533888U)) && |
|
481
|
2 |
0 |
if (n == ipow(root,13)) return 13; |
|
510
|
22 |
10442 |
if (a > 0) { |
|
511
|
22 |
0 |
if (a == 1 || n <= 1) return 1; |
|
|
3 |
19 |
if (a == 1 || n <= 1) return 1; |
|
512
|
17 |
2 |
if ((a % 2) == 0) |
|
513
|
4 |
13 |
return !is_perfect_square(n) ? 0 : (a == 2) ? 1 : is_power(isqrt(n),a>>1); |
|
|
0 |
4 |
return !is_perfect_square(n) ? 0 : (a == 2) ? 1 : is_power(isqrt(n),a>>1); |
|
514
|
2 |
0 |
if ((a % 3) == 0) |
|
515
|
2 |
0 |
return !is_perfect_cube(n) ? 0 : (a == 3) ? 1 : is_power(icbrt(n),a/3); |
|
|
0 |
2 |
return !is_perfect_cube(n) ? 0 : (a == 3) ? 1 : is_power(icbrt(n),a/3); |
|
516
|
0 |
0 |
if ((a % 5) == 0) |
|
517
|
0 |
0 |
return !is_perfect_fifth(n) ? 0 : (a == 5) ? 1 :is_power(rootof(n,5),a/5); |
|
|
0 |
0 |
return !is_perfect_fifth(n) ? 0 : (a == 5) ? 1 :is_power(rootof(n,5),a/5); |
|
520
|
0 |
10442 |
if (a != 0) return !(ret % a); /* Is the max power divisible by a? */ |
|
521
|
152 |
10290 |
return (ret == 1) ? 0 : ret; |
|
534
|
0 |
461 |
if (k == 0) return 0; |
|
535
|
19 |
442 |
if (k == 1) return n; |
|
536
|
116 |
326 |
if (k == 2) return isqrt(n); |
|
537
|
8 |
318 |
if (k == 3) return icbrt(n); |
|
540
|
316 |
2 |
max = 1 + ((k >= ROOT_MAX_3) ? 2 : root_max[k]); |
|
541
|
318 |
0 |
lo = UVCONST(1) << (log2floor(n)/k); |
|
545
|
798 |
318 |
while (lo < hi) { |
|
547
|
443 |
355 |
if (ipow(mid,k) <= n) lo = mid+1; |
|
556
|
6 |
10268 |
if (n < 2) return 0; |
|
558
|
24 |
10244 |
if (!(n&1)) { |
|
559
|
15 |
9 |
if (n & (n-1)) return 0; |
|
561
|
9 |
0 |
return ctz(n); |
|
563
|
15 |
10229 |
if ((n%3) == 0) { |
|
565
|
145 |
11 |
do { n /= 3; power++; } while (n > 1 && (n%3) == 0); |
|
|
141 |
4 |
do { n /= 3; power++; } while (n > 1 && (n%3) == 0); |
|
566
|
4 |
11 |
if (n != 1) return 0; |
|
570
|
2007 |
8222 |
if ((n%5) == 0) { |
|
571
|
2563 |
10 |
do { n /= 5; power++; } while (n > 1 && (n%5) == 0); |
|
|
566 |
1997 |
do { n /= 5; power++; } while (n > 1 && (n%5) == 0); |
|
572
|
1997 |
10 |
if (n != 1) return 0; |
|
576
|
1149 |
7073 |
if ((n%7) == 0) { |
|
577
|
1394 |
9 |
do { n /= 7; power++; } while (n > 1 && (n%7) == 0); |
|
|
254 |
1140 |
do { n /= 7; power++; } while (n > 1 && (n%7) == 0); |
|
578
|
1140 |
9 |
if (n != 1) return 0; |
|
582
|
2690 |
4383 |
if (is_prob_prime(n)) |
|
586
|
4262 |
121 |
if (power == 1) power = 0; |
|
587
|
121 |
4262 |
if (power) { |
|
589
|
103 |
18 |
if (is_prob_prime(root)) |
|
601
|
63 |
2 |
if (k < 2 || n < 2) return 0; |
|
|
8 |
55 |
if (k < 2 || n < 2) return 0; |
|
602
|
54 |
1 |
if (k == 2) return ctz(n); |
|
|
54 |
0 |
if (k == 2) return ctz(n); |
|
603
|
3 |
1 |
while ( !(n % kpower) ) { |
|
614
|
200 |
401 |
if (b == 2) |
|
615
|
200 |
0 |
return log2floor(n); |
|
616
|
0 |
401 |
if (n > UV_MAX/b) { |
|
620
|
1140 |
401 |
for (v = b; v <= n; v *= b) |
|
629
|
1 |
0 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
1 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
1 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
1 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
634
|
0 |
1 |
Newz(0, s, slen, uint32_t); |
|
635
|
7 |
1 |
for (i = 0; i < slen; i++) { /* Chunks of 8 digits */ |
|
636
|
52 |
6 |
for (j = 0, d = 0, power = 1; j < 8 && len > 0; j++, power *= 10) { |
|
|
51 |
1 |
for (j = 0, d = 0, power = 1; j < 8 && len > 0; j++, power *= 10) { |
|
638
|
0 |
51 |
if (v > 9) croak("Parameter '%s' must be a positive integer",ptr); |
|
644
|
143 |
1 |
while (slen > 1) { |
|
645
|
71 |
72 |
if (s[slen-1] & 1) count++; |
|
647
|
6 |
137 |
if (s[0] == 1) { |
|
648
|
0 |
6 |
if (--slen == 0) break; |
|
651
|
596 |
143 |
for (i = 0; i < slen; i++) { |
|
652
|
453 |
143 |
if ( (i+1) < slen && sptr[i] & 1 ) sptr[i+1] += 100000000; |
|
|
239 |
214 |
if ( (i+1) < slen && sptr[i] & 1 ) sptr[i+1] += 100000000; |
|
657
|
27 |
1 |
for (d = s[0]; d > 0; d >>= 1) |
|
658
|
12 |
15 |
if (d & 1) |
|
670
|
3619 |
1282 |
while (a) { |
|
671
|
3619 |
0 |
int r = padic2(a); |
|
672
|
1637 |
1982 |
if (r) { |
|
673
|
1095 |
542 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
|
789 |
306 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
|
150 |
639 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
676
|
416 |
3203 |
if (a & b & 2) s = -s; |
|
679
|
1235 |
47 |
return (b == 1) ? s : 0; |
|
684
|
1246 |
42 |
if (b & 1) return kronecker_uu_sign(a, b, 1); |
|
685
|
18 |
24 |
if (!(a&1)) return 0; |
|
687
|
23 |
1 |
r = padic2(b); |
|
688
|
24 |
0 |
if (r) { |
|
689
|
22 |
2 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
11 |
11 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
5 |
6 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
697
|
35 |
14 |
if (a >= 0) return kronecker_uu(a, b); |
|
698
|
2 |
12 |
if (b == 0) return (a == 1 || a == -1) ? 1 : 0; |
|
|
2 |
0 |
if (b == 0) return (a == 1 || a == -1) ? 1 : 0; |
|
|
1 |
1 |
if (b == 0) return (a == 1 || a == -1) ? 1 : 0; |
|
700
|
12 |
0 |
r = padic2(b); |
|
701
|
2 |
10 |
if (r) { |
|
702
|
0 |
2 |
if (!(a&1)) return 0; |
|
703
|
2 |
0 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
2 |
0 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
2 |
0 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
707
|
8 |
4 |
if (a < 0) a += b; |
|
712
|
7 |
11 |
if (a >= 0 && b >= 0) |
|
|
0 |
7 |
if (a >= 0 && b >= 0) |
|
713
|
0 |
0 |
return (b & 1) ? kronecker_uu_sign(a, b, 1) : kronecker_uu(a,b); |
|
714
|
7 |
11 |
if (b >= 0) |
|
716
|
4 |
7 |
return kronecker_su(a, -b) * ((a < 0) ? -1 : 1); |
|
721
|
717 |
2490 |
if ( (n > 12 && sizeof(UV) <= 4) || (n > 20 && sizeof(UV) <= 8) ) return 0; |
|
722
|
15771 |
2490 |
for (i = 2; i <= n; i++) |
|
729
|
186 |
24938 |
if (k == 0) return 1; |
|
730
|
2034 |
22904 |
if (k == 1) return n; |
|
731
|
1553 |
21351 |
if (k >= n) return (k == n); |
|
732
|
10633 |
10718 |
if (k > n/2) k = n-k; |
|
733
|
197192 |
16115 |
for (d = 1; d <= k; d++) { |
|
734
|
14824 |
182368 |
if (r >= UV_MAX/n) { /* Possible overflow */ |
|
738
|
5236 |
9588 |
if (r >= UV_MAX/nr) return 0; /* Unavoidable overflow */ |
|
753
|
0 |
190 |
if (m == n) return 1; |
|
754
|
190 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
190 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
0 |
190 |
if (n == 0 || m == 0 || m > n) return 0; |
|
755
|
19 |
171 |
if (m == 1) return factorial(n); |
|
758
|
0 |
171 |
if (f1 == 0) return 0; |
|
760
|
171 |
0 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
|
0 |
171 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
763
|
171 |
0 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
|
5 |
166 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
771
|
0 |
1789 |
if (m == n) return 1; |
|
772
|
1789 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
1789 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
0 |
1789 |
if (n == 0 || m == 0 || m > n) return 0; |
|
773
|
240 |
1549 |
if (m == 1) return 1; |
|
775
|
165 |
1384 |
if ((f = factorial(m)) == 0) return 0; |
|
776
|
6586 |
1075 |
for (j = 1; j <= (IV)m; j++) { |
|
778
|
115103 |
6277 |
for (k = 1; k <= (IV)n; k++) { |
|
779
|
115103 |
0 |
if (t == 0 || j >= IV_MAX/t) return 0; |
|
|
309 |
114794 |
if (t == 0 || j >= IV_MAX/t) return 0; |
|
782
|
2890 |
3387 |
if ((m-j) & 1) t *= -1; |
|
791
|
0 |
192 |
if (m == n) return 1; |
|
792
|
192 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
192 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
0 |
192 |
if (n == 0 || m == 0 || m > n) return 0; |
|
793
|
19 |
173 |
if (m == 1) { |
|
795
|
0 |
19 |
if (f>(UV)IV_MAX) return 0; |
|
796
|
10 |
9 |
return (n&1) ? ((IV)f) : -((IV)f); |
|
799
|
816 |
126 |
for (k = 1; k <= (IV)(n-m); k++) { |
|
803
|
814 |
2 |
if (b1 == 0 || b2 == 0 || s2 == 0 || b1 > IV_MAX/b2) return 0; |
|
|
814 |
0 |
if (b1 == 0 || b2 == 0 || s2 == 0 || b1 > IV_MAX/b2) return 0; |
|
|
804 |
10 |
if (b1 == 0 || b2 == 0 || s2 == 0 || b1 > IV_MAX/b2) return 0; |
|
|
0 |
804 |
if (b1 == 0 || b2 == 0 || s2 == 0 || b1 > IV_MAX/b2) return 0; |
|
805
|
35 |
769 |
if (s2 > IV_MAX/t) return 0; |
|
807
|
430 |
339 |
s += (k & 1) ? -t : t; |
|
814
|
96 |
613 |
if (n <= 1) return n; |
|
817
|
144 |
613 |
while ((n & 0x3) == 0) { n >>= 1; totient <<= 1; } |
|
818
|
332 |
281 |
if ((n & 0x1) == 0) { n >>= 1; } |
|
822
|
648 |
613 |
for (i = 0; i < nfacs; i++) { |
|
824
|
48 |
600 |
if (f == lastf) { totient *= f; } |
|
840
|
490 |
0 |
if (k == 0 || n <= 1) return (n == 1); |
|
|
11 |
479 |
if (k == 0 || n <= 1) return (n == 1); |
|
841
|
457 |
22 |
if (k > 6 || (k > 1 && n >= jordan_overflow[k-2])) return 0; |
|
|
321 |
136 |
if (k > 6 || (k > 1 && n >= jordan_overflow[k-2])) return 0; |
|
|
0 |
321 |
if (k > 6 || (k > 1 && n >= jordan_overflow[k-2])) return 0; |
|
845
|
205 |
457 |
while ((n & 0x3) == 0) { n >>= 1; totient *= (1<
|
|
846
|
226 |
231 |
if ((n & 0x1) == 0) { n >>= 1; totient *= ((1<
|
|
848
|
503 |
457 |
for (i = 0; i < nfac; i++) { |
|
852
|
170 |
410 |
while (i+1 < nfac && p == factors[i+1]) { |
|
|
77 |
93 |
while (i+1 < nfac && p == factors[i+1]) { |
|
865
|
8 |
262 |
if (n < 8) return totient(n); |
|
866
|
9 |
253 |
if ((n & (n-1)) == 0) return n >> 2; |
|
868
|
253 |
0 |
i = ctz(n); |
|
869
|
95 |
158 |
if (i > 0) { |
|
871
|
20 |
75 |
lambda <<= (i>2) ? i-2 : i-1; |
|
874
|
347 |
253 |
for (i = 0; i < nfactors; i++) { |
|
876
|
141 |
253 |
while (i+1 < nfactors && p == fac[i+1]) { |
|
|
47 |
94 |
while (i+1 < nfactors && p == fac[i+1]) { |
|
891
|
19440 |
560 |
if (n < 561 || !(n&1)) return 0; |
|
|
9720 |
9720 |
if (n < 561 || !(n&1)) return 0; |
|
894
|
8640 |
1080 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
8294 |
346 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
8125 |
169 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
8058 |
67 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
47 |
8011 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
898
|
1333 |
6678 |
if (!(n% 5) && ((n-1) % 4 != 0)) return 0; |
|
|
666 |
667 |
if (!(n% 5) && ((n-1) % 4 != 0)) return 0; |
|
899
|
918 |
6427 |
if (!(n% 7) && ((n-1) % 6 != 0)) return 0; |
|
|
574 |
344 |
if (!(n% 7) && ((n-1) % 6 != 0)) return 0; |
|
900
|
567 |
6204 |
if (!(n%11) && ((n-1) % 10 != 0)) return 0; |
|
|
438 |
129 |
if (!(n%11) && ((n-1) % 10 != 0)) return 0; |
|
901
|
451 |
5882 |
if (!(n%13) && ((n-1) % 12 != 0)) return 0; |
|
|
349 |
102 |
if (!(n%13) && ((n-1) % 12 != 0)) return 0; |
|
902
|
355 |
5629 |
if (!(n%17) && ((n-1) % 16 != 0)) return 0; |
|
|
306 |
49 |
if (!(n%17) && ((n-1) % 16 != 0)) return 0; |
|
903
|
302 |
5376 |
if (!(n%19) && ((n-1) % 18 != 0)) return 0; |
|
|
261 |
41 |
if (!(n%19) && ((n-1) % 18 != 0)) return 0; |
|
904
|
244 |
5173 |
if (!(n%23) && ((n-1) % 22 != 0)) return 0; |
|
|
220 |
24 |
if (!(n%23) && ((n-1) % 22 != 0)) return 0; |
|
907
|
0 |
5197 |
if (n > 5000000) { |
|
908
|
0 |
0 |
if (!(n%29) && ((n-1) % 28 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%29) && ((n-1) % 28 != 0)) return 0; |
|
909
|
0 |
0 |
if (!(n%31) && ((n-1) % 30 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%31) && ((n-1) % 30 != 0)) return 0; |
|
910
|
0 |
0 |
if (!(n%37) && ((n-1) % 36 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%37) && ((n-1) % 36 != 0)) return 0; |
|
911
|
0 |
0 |
if (!(n%41) && ((n-1) % 40 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%41) && ((n-1) % 40 != 0)) return 0; |
|
912
|
0 |
0 |
if (!(n%43) && ((n-1) % 42 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%43) && ((n-1) % 42 != 0)) return 0; |
|
913
|
0 |
0 |
if (!is_pseudoprime(n,2)) return 0; |
|
917
|
4664 |
533 |
if (nfactors < 3) |
|
919
|
1321 |
9 |
for (i = 0; i < nfactors; i++) { |
|
920
|
1321 |
0 |
if (exp[i] > 1 || ((n-1) % (fac[i]-1)) != 0) |
|
|
524 |
797 |
if (exp[i] > 1 || ((n-1) % (fac[i]-1)) != 0) |
|
928
|
13015 |
144 |
for (i = 0; i < nfactors; i++) { |
|
930
|
13015 |
0 |
if (d == 0 || (p % d) != 0) |
|
|
8086 |
4929 |
if (d == 0 || (p % d) != 0) |
|
942
|
68 |
5334 |
if (n < 35) return 0; |
|
945
|
4000 |
1334 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
3556 |
444 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
3414 |
142 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
3343 |
71 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
3313 |
30 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
20 |
3293 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
950
|
741 |
2552 |
if (nfactors < 2) |
|
953
|
6371 |
2518 |
for (i = 0; i < nfactors; i++) |
|
954
|
34 |
6337 |
if (exp[i] > 1) |
|
962
|
1448 |
1070 |
if (nfactors == 2) { |
|
964
|
5953 |
0 |
for (i = 0; i < (int)ndivisors; i++) { |
|
967
|
1448 |
4505 |
if (d >= spf) break; |
|
968
|
92 |
4413 |
if (is_quasi_base(nfactors, fac, n-k, k)) |
|
973
|
8453 |
1070 |
for (i = 0; i < (int)ndivisors; i++) { |
|
976
|
3693 |
4760 |
if (lpf > d && k >= spf) continue; |
|
|
3658 |
35 |
if (lpf > d && k >= spf) continue; |
|
977
|
3725 |
1070 |
if (k != 0 && is_quasi_base(nfactors, fac, n-k, k)) |
|
|
52 |
3673 |
if (k != 0 && is_quasi_base(nfactors, fac, n-k, k)) |
|
988
|
0 |
103 |
if (n < 6) return (n == 4); |
|
989
|
51 |
52 |
if (!(n&1)) return !!is_prob_prime(n>>1); |
|
990
|
16 |
36 |
if (!(n%3)) return !!is_prob_prime(n/3); |
|
991
|
6 |
30 |
if (!(n%5)) return !!is_prob_prime(n/5); |
|
994
|
244 |
2 |
for (sp = 4; sp < 60; sp++) { |
|
996
|
18 |
226 |
if (p > n3) |
|
998
|
10 |
216 |
if ((n % p) == 0) |
|
1002
|
11 |
9 |
if (is_prob_prime(n)) return 0; |
|
1003
|
7 |
2 |
if (p > n3) return 1; |
|
1006
|
0 |
2 |
if ( pbrent_factor(n, factors, 70000, 1) == 2 |
|
1008
|
0 |
0 |
|| pminus1_factor(n, factors, 4000, 4000) == 2 |
|
1010
|
0 |
0 |
|| pbrent_factor(n, factors, 180000, 7) == 2 ) |
|
1011
|
2 |
0 |
return (is_prob_prime(factors[0]) && is_prob_prime(factors[1])); |
|
|
2 |
0 |
return (is_prob_prime(factors[0]) && is_prob_prime(factors[1])); |
|
1021
|
94 |
8 |
if (r) { |
|
1022
|
47 |
47 |
if (!neg) { |
|
1024
|
6 |
3 |
case 0: return (r == 4) ? 0 : is_square_free(n >> 2); |
|
|
6 |
0 |
case 0: return (r == 4) ? 0 : is_square_free(n >> 2); |
|
1030
|
6 |
3 |
case 0: return (r == 12) ? 0 : is_square_free(n >> 2); |
|
|
5 |
1 |
case 0: return (r == 12) ? 0 : is_square_free(n >> 2); |
|
1041
|
0 |
1 |
if (n == 0) return 0; |
|
1042
|
25838 |
0 |
for (v = 8; v < n-1 && fac != 0; v++) { |
|
|
25838 |
0 |
for (v = 8; v < n-1 && fac != 0; v++) { |
|
1043
|
25838 |
0 |
fac = (n < HALF_WORD) ? (fac*v) % n : mulmod(fac,v,n); |
|
1044
|
1 |
25837 |
if (fac == n-1 && (n % v) != 1) |
|
|
1 |
0 |
if (fac == n-1 && (n % v) != 1) |
|
1055
|
258 |
28755 |
if (n <= 1) return (int)n; |
|
1056
|
26934 |
1821 |
if ( n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49)) ) |
|
|
20203 |
6731 |
if ( n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49)) ) |
|
|
17955 |
2248 |
if ( n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49)) ) |
|
|
17232 |
723 |
if ( n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49)) ) |
|
|
363 |
16869 |
if ( n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49)) ) |
|
1060
|
21533 |
17624 |
for (i = 1; i < nfactors; i++) |
|
1061
|
1066 |
20467 |
if (factors[i] == factors[i-1]) |
|
1063
|
9056 |
8568 |
return (nfactors % 2) ? -1 : 1; |
|
1068
|
6 |
14 |
if (!primepower(n,&p)) return 1; /* Not a prime power */ |
|
1079
|
6 |
69 |
if (n <= 1) return n; /* znorder(x,0) = 0, znorder(x,1) = 1 */ |
|
1080
|
3 |
66 |
if (a <= 1) return a; /* znorder(0,x) = 0, znorder(1,x) = 1 (x > 1) */ |
|
1081
|
6 |
60 |
if (gcd_ui(a,n) > 1) return 0; |
|
1087
|
219 |
60 |
for (i = 0; i < nfactors; i++) { |
|
1092
|
168 |
219 |
for (ek = 0; a1 != 1 && ek++ <= ei; a1 = powmod(a1, pi, n)) |
|
|
168 |
0 |
for (ek = 0; a1 != 1 && ek++ <= ei; a1 = powmod(a1, pi, n)) |
|
1094
|
0 |
219 |
if (ek > ei) return 0; |
|
1105
|
5 |
20 |
if (n <= 4) return (n == 0) ? 0 : n-1; |
|
|
4 |
1 |
if (n <= 4) return (n == 0) ? 0 : n-1; |
|
1106
|
1 |
19 |
if (n % 4 == 0) return 0; |
|
1108
|
3 |
16 |
on = (n&1) ? n : (n>>1); |
|
1111
|
2 |
17 |
if (!is_prob_prime(r)) return 0; /* c^a or 2c^a */ |
|
1115
|
66 |
17 |
for (i = 0; i < nfactors; i++) |
|
1117
|
870 |
0 |
for (a = 2; a < n; a++) { |
|
1119
|
859 |
11 |
if (a == 4 || a == 8 || a == 9) continue; |
|
|
852 |
7 |
if (a == 4 || a == 8 || a == 9) continue; |
|
|
7 |
845 |
if (a == 4 || a == 8 || a == 9) continue; |
|
1121
|
812 |
33 |
if (phi == n-1) { |
|
1122
|
653 |
159 |
if (kronecker_uu(a, n) != -1) continue; |
|
1124
|
16 |
17 |
if (kronecker_uu(a, n) == 0) continue; |
|
1126
|
442 |
17 |
for (i = 0; i < nfactors; i++) |
|
1127
|
159 |
283 |
if (powmod(a, exp[i], n) == 1) |
|
1129
|
17 |
159 |
if (i == nfactors) return a; |
|
1137
|
2 |
44 |
if (n <= 1) return n; |
|
1138
|
20 |
24 |
if (a >= n) a %= n; |
|
1139
|
2 |
42 |
if (gcd_ui(a,n) != 1) return 0; |
|
1140
|
19 |
23 |
s = nprime ? n-1 : totient(n); |
|
1144
|
5 |
37 |
if (i > 1 && gcd_ui(i, s) != 1) return 0; |
|
|
4 |
1 |
if (i > 1 && gcd_ui(i, s) != 1) return 0; |
|
1147
|
37 |
1 |
if ((s % 2) == 0 && powmod(a, s/2, n) == 1) return 0; |
|
|
9 |
28 |
if ((s % 2) == 0 && powmod(a, s/2, n) == 1) return 0; |
|
1161
|
10 |
19 |
if ((s % 3) == 0 && mont_powmod(a, s/3, n) == mont1) return 0; |
|
|
1 |
9 |
if ((s % 3) == 0 && mont_powmod(a, s/3, n) == mont1) return 0; |
|
1162
|
13 |
15 |
if ((s % 5) == 0 && mont_powmod(a, s/5, n) == mont1) return 0; |
|
|
0 |
13 |
if ((s % 5) == 0 && mont_powmod(a, s/5, n) == mont1) return 0; |
|
1164
|
80 |
28 |
for (i = 0; i < nfacs; i++) { |
|
1165
|
31 |
49 |
if (fac[i] > 5 && mont_powmod(a, s/fac[i], n) == mont1) return 0; |
|
|
0 |
31 |
if (fac[i] > 5 && mont_powmod(a, s/fac[i], n) == mont1) return 0; |
|
1176
|
3 |
47 |
if (a == 0 && b == 0) { os = 0; t = 0; } |
|
|
1 |
2 |
if (a == 0 && b == 0) { os = 0; t = 0; } |
|
1177
|
285 |
50 |
while (r != 0) { |
|
1183
|
4 |
46 |
if (or < 0) /* correct sign */ |
|
1185
|
50 |
0 |
if (u != 0) *u = os; |
|
1186
|
50 |
0 |
if (v != 0) *v = ot; |
|
1187
|
38 |
12 |
if (cs != 0) *cs = s; |
|
1188
|
38 |
12 |
if (ct != 0) *ct = t; |
|
1196
|
11596 |
429 |
while (nr != 0) { |
|
1201
|
122 |
307 |
if (r > 1) return 0; /* No inverse */ |
|
1202
|
160 |
147 |
if (t < 0) t += n; |
|
1208
|
0 |
2 |
if (binv == 0) return 0; |
|
1214
|
0 |
0 |
do { d /= p; e += d; } while (d > 0); |
|
1221
|
1275 |
0 |
if (n >= m || m == 1) return 0; |
|
|
1 |
1274 |
if (n >= m || m == 1) return 0; |
|
1223
|
494 |
780 |
if (n <= 10) { /* Keep things simple for small n */ |
|
1224
|
1793 |
413 |
for (i = 2; i <= n && res != 0; i++) |
|
|
1712 |
81 |
for (i = 2; i <= n && res != 0; i++) |
|
1229
|
555 |
225 |
if (n > m/2 && is_prime(m)) /* Check if we can go backwards */ |
|
|
138 |
417 |
if (n > m/2 && is_prime(m)) /* Check if we can go backwards */ |
|
1231
|
20 |
760 |
if (d < 2) |
|
1232
|
10 |
10 |
return (d == 0) ? m-1 : 1; /* Wilson's Theorem: n = m-1 and n = m-2 */ |
|
1234
|
642 |
118 |
if (d == n && d > 5000000) { /* Check for composite m that leads to 0 */ |
|
|
0 |
642 |
if (d == n && d > 5000000) { /* Check for composite m that leads to 0 */ |
|
1237
|
0 |
0 |
if (n >= facs[nfacs-1]) return 0; |
|
1241
|
360 |
400 |
if (m & 1 && d < 40000) { |
|
|
360 |
0 |
if (m & 1 && d < 40000) { |
|
1245
|
3582 |
178 |
for (i = 2; i <= d && res != 0; i++) { |
|
|
3400 |
182 |
for (i = 2; i <= d && res != 0; i++) { |
|
1247
|
0 |
3400 |
res = mont_mulmod(res,monti,m); |
|
1249
|
0 |
360 |
res = mont_recover(res, m); |
|
1252
|
400 |
0 |
if (d < 10000) { |
|
1253
|
3916 |
34 |
for (i = 2; i <= d && res != 0; i++) |
|
|
3550 |
366 |
for (i = 2; i <= d && res != 0; i++) |
|
1266
|
0 |
0 |
for (i = 1; i <= 3; i++) /* Handle 2,3,5 assume d>10*/ |
|
1268
|
0 |
0 |
while (res != 0 && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
|
0 |
0 |
while (res != 0 && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
1269
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
1270
|
0 |
0 |
UV k = (p > (d>>1)) ? p : _powfactor(p, d, m); |
|
1272
|
0 |
0 |
if (res == 0) break; |
|
1279
|
118 |
642 |
if (d != n && res != 0) { /* Handle backwards case */ |
|
|
118 |
0 |
if (d != n && res != 0) { /* Handle backwards case */ |
|
1280
|
61 |
57 |
if (!(d&1)) res = submod(m,res,m); |
|
1288
|
8 |
7 |
if (p-s < s) s = p-s; |
|
1289
|
0 |
15 |
if (mulmod(s, s, p) != a) return 0; |
|
1363
|
1 |
7 |
if ((p % 4) == 3) { |
|
1365
|
0 |
1 |
return mont_recover(b, p); |
|
1368
|
5 |
2 |
if ((p % 8) == 5) { /* Atkin's algorithm. Faster than Legendre. */ |
|
1372
|
0 |
5 |
beta = mont_mulmod(a2,mont_sqrmod(alpha,p),p); |
|
|
0 |
0 |
beta = mont_mulmod(a2,mont_sqrmod(alpha,p),p); |
|
|
0 |
5 |
beta = mont_mulmod(a2,mont_sqrmod(alpha,p),p); |
|
1374
|
0 |
5 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
|
0 |
0 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
|
0 |
5 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
1375
|
0 |
5 |
return mont_recover(b, p); |
|
1377
|
1 |
1 |
if ((p % 16) == 9) { /* Müller's algorithm extending Atkin */ |
|
1381
|
0 |
1 |
beta = mont_mulmod(a2, mont_sqrmod(alpha,p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_sqrmod(alpha,p), p); |
|
|
0 |
1 |
beta = mont_mulmod(a2, mont_sqrmod(alpha,p), p); |
|
1382
|
0 |
1 |
if (mont_sqrmod(beta,p) != submod(0,mont1,p)) { |
|
|
1 |
0 |
if (mont_sqrmod(beta,p) != submod(0,mont1,p)) { |
|
1383
|
4 |
1 |
do { d += 2; } while (kronecker_uu(d,p) != -1 && d < p); |
|
|
4 |
0 |
do { d += 2; } while (kronecker_uu(d,p) != -1 && d < p); |
|
1385
|
0 |
1 |
alpha = mont_mulmod(alpha, mont_powmod(d,(p-9)>>3,p), p); |
|
1386
|
0 |
1 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
1 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
1 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
1 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
1387
|
0 |
1 |
beta = mont_mulmod(submod(beta,mont1,p), d, p); |
|
1391
|
0 |
1 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
|
0 |
0 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
|
0 |
1 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
1392
|
0 |
1 |
return mont_recover(b, p); |
|
1396
|
1 |
0 |
if ((p & 1) && mont_powmod(a,(p-1)>>1,p) != mont1) return 0; |
|
|
0 |
1 |
if ((p & 1) && mont_powmod(a,(p-1)>>1,p) != mont1) return 0; |
|
1404
|
0 |
1 |
while (kronecker_uu(t, p) != -1) { |
|
1406
|
0 |
0 |
if (t == 201) { /* exit if p looks like a composite */ |
|
1407
|
0 |
0 |
if ((p % 2) == 0 || powmod(2, p-1, p) != 1 || powmod(3, p-1, p) != 1) |
|
|
0 |
0 |
if ((p % 2) == 0 || powmod(2, p-1, p) != 1 || powmod(3, p-1, p) != 1) |
|
|
0 |
0 |
if ((p % 2) == 0 || powmod(2, p-1, p) != 1 || powmod(3, p-1, p) != 1) |
|
1409
|
0 |
0 |
} else if (t >= 20000) { /* should never happen */ |
|
1419
|
2 |
1 |
while (b != mont1) { |
|
1421
|
5 |
0 |
for (m = 0; m < r && t != mont1; m++) |
|
|
3 |
2 |
for (m = 0; m < r && t != mont1; m++) |
|
1422
|
0 |
3 |
t = mont_sqrmod(t, p); |
|
1423
|
0 |
2 |
if (m >= r) break; |
|
1425
|
0 |
2 |
x = mont_mulmod(x, t, p); |
|
1426
|
0 |
2 |
z = mont_mulmod(t, t, p); |
|
1427
|
0 |
2 |
b = mont_mulmod(b, z, p); |
|
1430
|
0 |
1 |
return mont_recover(x, p); |
|
1437
|
0 |
10 |
if (p == 0) return 0; |
|
1438
|
2 |
8 |
if (a >= p) a %= p; |
|
1439
|
10 |
0 |
if (p <= 2 || a <= 1) return verify_sqrtmod(a, s,a,p); |
|
|
2 |
8 |
if (p <= 2 || a <= 1) return verify_sqrtmod(a, s,a,p); |
|
1451
|
2 |
5 |
if (n == 0) return 0; |
|
1452
|
0 |
5 |
if (a >= n) a %= n; |
|
1453
|
3 |
2 |
if (n <= 2 || a <= 1) return verify_sqrtmod(a, s,a,n); |
|
|
0 |
3 |
if (n <= 2 || a <= 1) return verify_sqrtmod(a, s,a,n); |
|
1456
|
3 |
0 |
if (kronecker_uu(a, ((n%4) == 2) ? n/2 : n) == -1) return 0; |
|
|
0 |
3 |
if (kronecker_uu(a, ((n%4) == 2) ? n/2 : n) == -1) return 0; |
|
1459
|
0 |
3 |
if ((n % 4) == 0) { |
|
1460
|
0 |
0 |
if ((n % 8) == 0) { |
|
1461
|
0 |
0 |
if ((a % 8) != 1) return 0; |
|
1463
|
0 |
0 |
if ((a % 4) != 1) return 0; |
|
1469
|
0 |
3 |
if (gcdan == 1) { |
|
1470
|
0 |
0 |
if ((n % 3) == 0 && kronecker_uu(a, 3) != 1) return 0; |
|
|
0 |
0 |
if ((n % 3) == 0 && kronecker_uu(a, 3) != 1) return 0; |
|
1471
|
0 |
0 |
if ((n % 5) == 0 && kronecker_uu(a, 5) != 1) return 0; |
|
|
0 |
0 |
if ((n % 5) == 0 && kronecker_uu(a, 5) != 1) return 0; |
|
1472
|
0 |
0 |
if ((n % 7) == 0 && kronecker_uu(a, 7) != 1) return 0; |
|
|
0 |
0 |
if ((n % 7) == 0 && kronecker_uu(a, 7) != 1) return 0; |
|
1479
|
0 |
3 |
if (gcdan == 1) { |
|
1480
|
0 |
0 |
for (i = 0; i < nfactors; i++) |
|
1481
|
0 |
0 |
if (fac[i] > 7 && kronecker_uu(a, fac[i]) != 1) return 0; |
|
|
0 |
0 |
if (fac[i] > 7 && kronecker_uu(a, fac[i]) != 1) return 0; |
|
1484
|
8 |
3 |
for (i = 0; i < nfactors; i++) { |
|
1487
|
3 |
5 |
if (fac[i] == 2) { |
|
1488
|
3 |
0 |
if (exp[i] == 1) { |
|
1490
|
0 |
0 |
} else if (exp[i] == 2) { |
|
1497
|
0 |
0 |
for (j = 2; j < exp[i]; j++) { |
|
1500
|
0 |
0 |
for (k = 0; k < nthis && nnext < 254; k++) { |
|
|
0 |
0 |
for (k = 0; k < nthis && nnext < 254; k++) { |
|
1502
|
0 |
0 |
if (sqrmod(r,p) == (a % p)) |
|
1504
|
0 |
0 |
if (sqrmod(p-r,p) == (a % p)) |
|
1507
|
0 |
0 |
if (nnext == 0) return 0; |
|
1510
|
0 |
0 |
for (k = 0; k < nnext; k++) |
|
1520
|
0 |
5 |
if (!sqrtmod(&(sqr[i]), a, p)) |
|
1524
|
0 |
5 |
for (j = 1; j < exp[i]; j++) { |
|
1531
|
0 |
0 |
if (expect != 1 || sqrmod(sol,p) != (a % p)) { |
|
|
0 |
0 |
if (expect != 1 || sqrmod(sol,p) != (a % p)) { |
|
1540
|
8 |
3 |
for (i = 0; i < nfactors; i++) |
|
1544
|
3 |
0 |
return (i == 1) ? verify_sqrtmod(p, s, a, n) : 0; |
|
1553
|
0 |
4 |
if (num == 0) return 0; |
|
1555
|
8 |
0 |
for (i = 0; i < num; i++) { |
|
1558
|
3 |
5 |
if (gcd != 1) return 0; /* not coprime */ |
|
1560
|
1 |
4 |
if (ni > (UV_MAX/lcm)) return 0; /* lcm overflow */ |
|
1563
|
0 |
0 |
for (i = 0; i < num; i++) { |
|
1567
|
0 |
0 |
if (inverse == 0) return 0; /* n's coprime so should never happen */ |
|
1580
|
1 |
29 |
if (num == 0) return 0; |
|
1583
|
319 |
29 |
for (gi = 0, gap = sgaps[gi]; gap >= 1; gap = sgaps[++gi]) { |
|
1584
|
42 |
319 |
for (i = gap; i < num; i++) { |
|
1586
|
54 |
30 |
for (j = i; j >= gap && n[j-gap] < tn; j -= gap) |
|
|
42 |
12 |
for (j = i; j >= gap && n[j-gap] < tn; j -= gap) |
|
1592
|
1 |
28 |
if (n[0] > IV_MAX) return _simple_chinese(a,n,num,status); |
|
1594
|
38 |
20 |
for (i = 1; i < num; i++) { |
|
1598
|
10 |
28 |
if (gcd != 1 && ((sum % gcd) != (a[i] % gcd))) { *status = -1; return 0; } |
|
|
5 |
5 |
if (gcd != 1 && ((sum % gcd) != (a[i] % gcd))) { *status = -1; return 0; } |
|
1599
|
18 |
15 |
if (s < 0) s = -s; |
|
1600
|
15 |
18 |
if (t < 0) t = -t; |
|
1601
|
3 |
30 |
if (s > (IV)(IV_MAX/lcm)) return _simple_chinese(a,n,num,status); |
|
1603
|
14 |
16 |
if (u < 0) u += lcm; |
|
1604
|
15 |
15 |
if (v < 0) v += lcm; |
|
1615
|
9 |
9 |
UV sqrtn = which ? isqrt(n) : 0; /* for theta, p <= sqrtn always false */ |
|
1618
|
14 |
4 |
if (n < 500) { |
|
1620
|
122 |
14 |
for (pi = 1; (p = nth_prime(pi)) <= n; pi++) { |
|
1622
|
8 |
114 |
if (p <= sqrtn) logp *= floorl(logn/logp+1e-15); |
|
1632
|
2 |
2 |
if (!which) { |
|
1640
|
6 |
4 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
1641
|
213914 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
4 |
213910 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
213910 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
213914 |
11316 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
11320 |
6 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
1643
|
250 |
213660 |
if (p <= sqrtn) logp *= floorl(logn/logp+1e-15); |
|
1682
|
0 |
234 |
if (x == 0) croak("Invalid input to ExponentialIntegral: x must be != 0"); |
|
1684
|
0 |
234 |
if (x >= 12000) return INFINITY; |
|
1685
|
0 |
234 |
if (x <= -12000) return 0; |
|
1687
|
1 |
233 |
if (x < -1) { |
|
1692
|
20 |
0 |
for (n = 1; n <= 100000; n++) { |
|
1700
|
1 |
19 |
if ( fabsl(val-old) <= LDBL_EPSILON*fabsl(val) ) |
|
1703
|
5 |
228 |
} else if (x < 0) { |
|
1722
|
228 |
0 |
} else if (x < (-2 * logl(LDBL_EPSILON))) { |
|
1725
|
15320 |
0 |
for (n = 2; n <= 200; n++) { |
|
1731
|
228 |
15092 |
if (term < LDBL_EPSILON*sum) break; |
|
1737
|
0 |
0 |
} else if (x >= 24) { |
|
1753
|
0 |
0 |
for (n = 0; n <= 8; n++) |
|
1761
|
0 |
0 |
for (n = 1; n <= 200; n++) { |
|
1764
|
0 |
0 |
if (term < LDBL_EPSILON*sum) break; |
|
1765
|
0 |
0 |
if (term < last_term) { |
|
1782
|
0 |
2234 |
if (x == 0) return 0; |
|
1783
|
0 |
2234 |
if (x == 1) return -INFINITY; |
|
1784
|
0 |
2234 |
if (x == 2) return li2; |
|
1785
|
0 |
2234 |
if (x < 0) croak("Invalid input to LogarithmicIntegral: x must be >= 0"); |
|
1786
|
0 |
2234 |
if (x >= LDBL_MAX) return INFINITY; |
|
1789
|
2234 |
0 |
if (x > 1) { |
|
1795
|
90097 |
0 |
for (n = 1, k = 0; n < 200; n++) { |
|
1800
|
45696 |
90097 |
for (; k <= (n - 1) / 2; k++) |
|
1804
|
2234 |
87863 |
if (fabsl(sum - old_sum) <= LDBL_EPSILON) break; |
|
1816
|
3 |
94 |
if (x <= 2) return x + (x > 0); |
|
1818
|
376 |
55 |
for (i = 0, t = lx*logl(x); i < 4; i++) { |
|
1821
|
282 |
94 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
|
39 |
243 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
1828
|
0 |
94 |
i = (x > 4e16) ? 2048 : 128; |
|
1829
|
0 |
94 |
if (Li(r-1) >= lx) { |
|
1830
|
0 |
0 |
while (Li(r-i) >= lx) r -= i; |
|
1831
|
0 |
0 |
for (i = i/2; i > 0; i /= 2) |
|
1832
|
0 |
0 |
if (Li(r-i) >= lx) r -= i; |
|
1834
|
0 |
94 |
while (Li(r+i-1) < lx) r += i; |
|
1835
|
658 |
94 |
for (i = i/2; i > 0; i /= 2) |
|
1836
|
0 |
658 |
if (Li(r+i-1) < lx) r += i; |
|
1844
|
0 |
23 |
if (x <= 2) return x + (x > 0); |
|
1852
|
89 |
13 |
for (i = 0; i < 4; i++) { |
|
1855
|
66 |
23 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
|
10 |
56 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
1944
|
0 |
2895 |
if (x < 0) croak("Invalid input to RiemannZeta: x must be >= 0"); |
|
1945
|
0 |
2895 |
if (x == 1) return INFINITY; |
|
1947
|
2891 |
4 |
if (x == (unsigned int)x) { |
|
1949
|
2891 |
0 |
if ((k >= 0) && (k < (int)NPRECALC_ZETA)) |
|
|
2 |
2889 |
if ((k >= 0) && (k < (int)NPRECALC_ZETA)) |
|
1954
|
2893 |
0 |
if (x >= 0.5 && x <= 5.0) { |
|
|
2 |
2891 |
if (x >= 0.5 && x <= 5.0) { |
|
1979
|
0 |
2891 |
if (x > 17000.0) |
|
2025
|
9244 |
2 |
for (i = 2; i < 11; i++) { |
|
2028
|
2889 |
6355 |
if (fabsl(b) < fabsl(LDBL_EPSILON * s)) |
|
2033
|
19 |
0 |
for (i = 0; i < 13; i++) { |
|
2039
|
2 |
17 |
if (fabsl(t) < fabsl(LDBL_EPSILON * s)) |
|
2053
|
0 |
123 |
if (x <= 0) croak("Invalid input to ReimannR: x must be > 0"); |
|
2055
|
2 |
121 |
if (x > 1e19) { |
|
2058
|
132 |
0 |
for (k = 2; k <= 100; k++) { |
|
2059
|
50 |
82 |
if (amob[k] == 0) continue; |
|
2062
|
0 |
82 |
if (part_term > LDBL_MAX) return INFINITY; |
|
2066
|
2 |
80 |
if (fabsl(sum - old_sum) <= LDBL_EPSILON) break; |
|
2076
|
9329 |
0 |
for (k = 1; k <= 10000; k++) { |
|
2077
|
6440 |
2889 |
ki = (k-1 < NPRECALC_ZETA) ? riemann_zeta_table[k-1] : ld_riemann_zeta(k+1); |
|
2083
|
121 |
9208 |
if (fabsl(sum - old_sum) <= LDBL_EPSILON) break; |
|
2091
|
2 |
6 |
if (x < -0.060) { /* Pade(3,2) */ |
|
2093
|
0 |
2 |
long double t = (ti <= 0.0L) ? 0.0L : sqrtl(ti); |
|
2097
|
2 |
4 |
} else if (x < 1.363) { /* Winitzki 2003 section 3.5 */ |
|
2100
|
0 |
4 |
} else if (x < 3.7) { /* Modification of Vargas 2013 */ |
|
2123
|
0 |
9 |
if (x < -0.36787944117145L) |
|
2125
|
1 |
8 |
if (x == 0.0L) return 0.0L; |
|
2130
|
0 |
8 |
if (w <= -1.0L) return -1.0L + 8*LDBL_EPSILON; |
|
2132
|
1 |
7 |
if (x < -0.36783) return w; |
|
2146
|
28 |
2 |
for (i = 0; i < 6 && w != 0.0L; i++) { |
|
|
28 |
0 |
for (i = 0; i < 6 && w != 0.0L; i++) { |
|
2154
|
5 |
23 |
if (fabsl(wen) <= 64*LDBL_EPSILON) break; |
|
2165
|
0 |
987 |
if (digits <= 0) return 0; |
|
2166
|
15 |
972 |
if (digits <= DBL_DIG && digits <= 18) { |
|
|
15 |
0 |
if (digits <= DBL_DIG && digits <= 18) { |
|
2174
|
0 |
972 |
New(0, a, c, IV); |
|
2177
|
1776026 |
972 |
for (b = 0; b < c; b++) a[b] = 20000000; |
|
2179
|
125887 |
729 |
while ((b = c -= 14) > 0 && i < digits) { |
|
|
125644 |
243 |
while ((b = c -= 14) > 0 && i < digits) { |
|
2181
|
148341500 |
125644 |
while (--b > 0) { |
|
2189
|
0 |
125644 |
if (d4 > 9999) { |
|
2192
|
0 |
0 |
for (b=i-1; out[b] == '0'+1; b--) { out[b]='0'; out[b-1]++; } |
|
2201
|
480 |
492 |
if (out[digits-1] >= '5') out[digits-2]++; /* Round */ |
|
2202
|
70 |
972 |
for (i = digits-2; out[i] == '9'+1; i--) /* Keep rounding */ |
|
2219
|
4 |
0 |
if (b == 0 || blen == 0) croak("Parameter must be a positive integer"); |
|
|
0 |
4 |
if (b == 0 || blen == 0) croak("Parameter must be a positive integer"); |
|
2221
|
4 |
0 |
if (b[0] == '-' || b[0] == '+') { b++; blen--; } |
|
|
0 |
4 |
if (b[0] == '-' || b[0] == '+') { b++; blen--; } |
|
2222
|
4 |
0 |
while (blen > 0 && *b == '0') { b++; blen--; } |
|
|
0 |
4 |
while (blen > 0 && *b == '0') { b++; blen--; } |
|
2223
|
80 |
4 |
for (i = 0; i < blen; i++) |
|
2224
|
0 |
80 |
if (!isDIGIT(b[i])) |
|
2226
|
4 |
0 |
if (blen == 0 || i < blen) |
|
|
0 |
4 |
if (blen == 0 || i < blen) |
|
2229
|
2 |
2 |
if (a == 0) return 1; |
|
2232
|
2 |
0 |
if (a[0] == '-' || a[0] == '+') { a++; alen--; } |
|
|
0 |
2 |
if (a[0] == '-' || a[0] == '+') { a++; alen--; } |
|
2233
|
2 |
0 |
while (alen > 0 && *a == '0') { a++; alen--; } |
|
|
0 |
2 |
while (alen > 0 && *a == '0') { a++; alen--; } |
|
2235
|
0 |
2 |
if (aneg != bneg) return min ? (bneg == 1) : (aneg == 1); |
|
|
0 |
0 |
if (aneg != bneg) return min ? (bneg == 1) : (aneg == 1); |
|
2236
|
0 |
2 |
if (aneg == 1) min = !min; |
|
2237
|
0 |
2 |
if (alen != blen) return min ? (alen > blen) : (blen > alen); |
|
|
0 |
0 |
if (alen != blen) return min ? (alen > blen) : (blen > alen); |
|
2239
|
2 |
0 |
for (i = 0; i < blen; i++) |
|
2240
|
2 |
0 |
if (a[i] != b[i]) |
|
2241
|
1 |
1 |
return min ? (a[i] > b[i]) : (b[i] > a[i]); |
|
2251
|
6 |
0 |
if (s[0] == '-' || s[0] == '+') s++; |
|
|
0 |
6 |
if (s[0] == '-' || s[0] == '+') s++; |
|
2252
|
0 |
6 |
while (s[0] == '0') s++; |
|
2257
|
34 |
5 |
for (i = 0, len = strlen(s); i < len; i++) { |
|
2259
|
34 |
0 |
int d = !isalnum(c) ? 255 : (c <= '9') ? c-'0' : (c <= 'Z') ? c-'A'+10 : c-'a'+10; |
|
|
20 |
14 |
int d = !isalnum(c) ? 255 : (c <= '9') ? c-'0' : (c <= 'Z') ? c-'A'+10 : c-'a'+10; |
|
|
0 |
14 |
int d = !isalnum(c) ? 255 : (c <= '9') ? c-'0' : (c <= 'Z') ? c-'A'+10 : c-'a'+10; |
|
2260
|
0 |
34 |
if (d >= base) croak("Invalid digit for base %d", base); |
|
2261
|
1 |
33 |
if (n > max) return 0; /* Overflow */ |
|
2272
|
13 |
0 |
if (len < 0 || len > BITS_PER_WORD) |
|
|
0 |
13 |
if (len < 0 || len > BITS_PER_WORD) |
|
2274
|
63 |
13 |
for (i = 0; i < len; i++) { |
|
2276
|
0 |
63 |
if (n > (UV_MAX-d)/base) break; /* overflow */ |
|
2289
|
0 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
|
0 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
|
0 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
|
0 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
2291
|
0 |
0 |
if (r[0] >= (UV) base) return 0; /* TODO: We don't apply extended carry */ |
|
2295
|
0 |
0 |
if (base == 2 || base == 16) { |
|
|
0 |
0 |
if (base == 2 || base == 16) { |
|
2297
|
0 |
0 |
*s++ = (base == 2) ? 'b' : 'x'; |
|
2299
|
0 |
0 |
for (i = 0; i < len; i++) { |
|
2301
|
0 |
0 |
s[i] = (d < 10) ? '0'+d : 'a'+d-10; |
|
2312
|
17 |
0 |
if (base < 2 || length > 128) return -1; |
|
|
0 |
17 |
if (base < 2 || length > 128) return -1; |
|
2314
|
10 |
7 |
if (base == 2) { |
|
2315
|
77 |
10 |
for (d = 0; n; n >>= 1) |
|
2318
|
24 |
7 |
for (d = 0; n; n /= base) |
|
2321
|
11 |
6 |
if (length < 0) length = d; |
|
2322
|
26 |
17 |
while (d < length) |
|
2332
|
0 |
3 |
if (len < 0) return -1; |
|
2333
|
0 |
3 |
if (base > 36) croak("invalid base for string: %d", base); |
|
2335
|
18 |
3 |
for (i = 0; i < len; i++) { |
|
2337
|
18 |
0 |
s[i] = (dig < 10) ? '0'+dig : 'a'+dig-10; |
|
2347
|
0 |
1 |
if (hi < 0) { |
|
2359
|
19 |
1 |
} while (sum); |
|
2380
|
10 |
1 |
for (i=0; i < slen/2; i++) { |
|
2386
|
0 |
1 |
if (isneg) { |
|
2387
|
0 |
0 |
for (i = slen; i > 0; i--) |
|
2402
|
473541 |
472642 |
while (n /= p) s += n % 2; |
|
2407
|
0 |
0 |
while (n /= p) s += n % 2; |
|
2411
|
428809 |
472642 |
if (p > a) { |
|
2414
|
472642 |
0 |
UV pow = (n <= 4294967295UL) ? _catalan_v32(a<<1,p) : _catalan_v(a<<1,p); |
|
2416
|
186211 |
286431 |
: (pow == 1) ? mulmod(m,p,n) |
|
2417
|
185962 |
249 |
: mulmod(m,powmod(p,pow,n),n); |
|
2422
|
13 |
5 |
while (n /= p) |
|
2423
|
0 |
13 |
if (n % 2) |
|
2431
|
3 |
0 |
if (n < 2 || ((n % 2) == 0 && n != 2)) return 0; |
|
|
0 |
3 |
if (n < 2 || ((n % 2) == 0 && n != 2)) return 0; |
|
|
0 |
0 |
if (n < 2 || ((n % 2) == 0 && n != 2)) return 0; |
|
2432
|
0 |
3 |
if (is_prob_prime(n)) return 1; |
|
2443
|
0 |
3 |
if (nfactors == 2 && (n < UVCONST(10000000000))) |
|
|
0 |
0 |
if (nfactors == 2 && (n < UVCONST(10000000000))) |
|
2446
|
5 |
3 |
for (i = 0; i < nfactors; i++) { |
|
2447
|
0 |
5 |
if (_catalan_vtest(a << 1, factors[i])) |
|
2459
|
16 |
3 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
2460
|
901445 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
3 |
901442 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
901442 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
901445 |
56364 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
56367 |
16 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
2466
|
1 |
2 |
return (a & 1) ? (m==(n-1)) : (m==1); |
|
2473
|
10 |
34744 |
if (x == 0) return y; |
|
2475
|
18990 |
15754 |
if (y & 1) { /* Optimize y odd */ |
|
2476
|
18990 |
0 |
x >>= ctz(x); |
|
2477
|
343695 |
18990 |
while (x != y) { |
|
2478
|
38031 |
305664 |
if (x < y) { y -= x; y >>= ctz(y); } |
|
|
38031 |
0 |
if (x < y) { y -= x; y >>= ctz(y); } |
|
2479
|
305664 |
0 |
else { x -= y; x >>= ctz(x); } |
|
2484
|
1 |
15753 |
if (y == 0) return x; |
|
2487
|
15753 |
0 |
x2 = ctz(x); |
|
2488
|
15753 |
0 |
y2 = ctz(y); |
|
2493
|
187241 |
15753 |
while (x != y) { |
|
2494
|
14430 |
172811 |
if (x < y) { |
|
2496
|
14430 |
0 |
y >>= ctz(y); |
|
2499
|
172811 |
0 |
x >>= ctz(x); |
|
2513
|
6 |
4 |
return (n < NTAU) ? tau_table[n] : 0; |
|
2520
|
4 |
401 |
if (lim*lim == b2) lim--; |
|
2521
|
43 |
362 |
if (s > lim) return 0; |
|
2523
|
337 |
25 |
if ((lim-s) < 70) { /* Iterate looking for divisors */ |
|
2524
|
6767 |
337 |
for (i = s; i <= lim; i++) |
|
2525
|
106 |
6661 |
if (b2 % i == 0) |
|
2529
|
56 |
0 |
for (i = 0; i < ndivisors && divs[i] <= lim; i++) |
|
|
31 |
25 |
for (i = 0; i < ndivisors && divs[i] <= lim; i++) |
|
2530
|
6 |
25 |
if (divs[i] >= s) |
|
2544
|
1 |
95 |
if (n == 0) return -1; |
|
2545
|
82 |
13 |
if (nmod4 == 1 || nmod4 == 2) return 0; |
|
|
8 |
74 |
if (nmod4 == 1 || nmod4 == 2) return 0; |
|
2546
|
1 |
73 |
if (n == 3) return 4; |
|
2553
|
18 |
55 |
if (b == 1) |
|
2557
|
405 |
73 |
for (; b2 = (n + b*b) >> 2, 3*b2 < n; b += 2) { |
|
2562
|
70 |
3 |
return 12*h + ((b2*3 == n) ? 4 : square && !(n&1) ? 6 : 0); |
|
|
11 |
59 |
return 12*h + ((b2*3 == n) ? 4 : square && !(n&1) ? 6 : 0); |
|
|
10 |
1 |
return 12*h + ((b2*3 == n) ? 4 : square && !(n&1) ? 6 : 0); |
|
2567
|
0 |
25300 |
MPUassert(k >= 3, "is_polygonal root < 3"); |
|
2569
|
46 |
25254 |
if (n <= 1) return n; |
|
2570
|
198 |
25056 |
if (k == 4) return is_perfect_square(n) ? isqrt(n) : 0; |
|
|
18 |
180 |
if (k == 4) return is_perfect_square(n) ? isqrt(n) : 0; |
|
2571
|
108 |
24948 |
if (k == 3) { |
|
2572
|
0 |
108 |
if (n >= UV_MAX/8) *overflow = 1; |
|
2576
|
24948 |
0 |
if (k > UV_MAX/k || n > UV_MAX/(8*k-16)) *overflow = 1; |
|
|
0 |
24948 |
if (k > UV_MAX/k || n > UV_MAX/(8*k-16)) *overflow = 1; |
|
2580
|
0 |
25056 |
if (D+R <= D) *overflow = 1; |
|
2582
|
25056 |
0 |
if (*overflow || !is_perfect_square(D)) return 0; |
|
|
24138 |
918 |
if (*overflow || !is_perfect_square(D)) return 0; |
|
2585
|
522 |
396 |
if ((D % R) != 0) return 0; |
|
2597
|
3 |
5 |
while (f == 0) /* We can handle n! overflow if we have a valid k */ |
|
2600
|
1 |
4 |
if (k/f >= (UV)n) |
|
2603
|
45 |
5 |
for (i = 0; i < n; i++) |
|
2605
|
37 |
5 |
for (i = si; i < n-1; i++) { |
|
2609
|
19 |
18 |
if (p > 0) { |
|
2610
|
47 |
19 |
for (j = i+p, t = vec[j]; j > i; j--) |
|
2622
|
2 |
4 |
if (f == 0) return 0; |
|
2623
|
38 |
4 |
for (i = 0; i < n-1; i++) { |
|
2624
|
302 |
38 |
for (j = i+1, k = 0; j < n; j++) |
|
2625
|
137 |
165 |
if (vec[j] < vec[i]) |
|
2627
|
0 |
38 |
if ((UV)k > (UV_MAX-num)/f) return 0; /* overflow */ |
|
2636
|
0 |
0 |
{ const UV *x = a, *y = b; return (*x > *y) ? 1 : (*x < *y) ? -1 : 0; } |
|
|
0 |
0 |
{ const UV *x = a, *y = b; return (*x > *y) ? 1 : (*x < *y) ? -1 : 0; } |
|
2651
|
0 |
3 |
if (k > n) k = n; |
|
2653
|
3 |
0 |
if (k == 0) { /* 0 of n */ |
|
2654
|
1 |
2 |
} else if (k == 1) { /* 1 of n. Pick one at random */ |
|
2656
|
0 |
2 |
} else if (k == 2 && n == 2) { /* 2 of 2. Flip a coin */ |
|
|
0 |
0 |
} else if (k == 2 && n == 2) { /* 2 of 2. Flip a coin */ |
|
2659
|
0 |
2 |
} else if (k == 2) { /* 2 of n. Pick 2 skipping dup */ |
|
2662
|
0 |
0 |
if (S[1] >= S[0]) S[1]++; |
|
2663
|
0 |
2 |
} else if (k < n/100 && k < 30) { /* k of n. Pick k with loop */ |
|
|
0 |
0 |
} else if (k < n/100 && k < 30) { /* k of n. Pick k with loop */ |
|
2664
|
0 |
0 |
for (i = 0; i < k; i++) { |
|
2667
|
0 |
0 |
for (j = 0; j < i; j++) |
|
2668
|
0 |
0 |
if (S[j] == S[i]) |
|
2670
|
0 |
0 |
} while (j < i); |
|
2672
|
0 |
2 |
} else if (k < n/100 && n > 1000000) {/* k of n. Pick k with dedup retry */ |
|
|
0 |
0 |
} else if (k < n/100 && n > 1000000) {/* k of n. Pick k with dedup retry */ |
|
2673
|
0 |
0 |
for (j = 0; j < k; ) { |
|
2674
|
0 |
0 |
for (i = j; i < k; i++) /* Fill S[j .. k-1] then sort S */ |
|
2677
|
0 |
0 |
for (j = 0, i = 1; i < k; i++) /* Find and remove dups. O(n). */ |
|
2678
|
0 |
0 |
if (S[j] != S[i]) |
|
2683
|
0 |
0 |
for (i = 0; i < k; i++) { |
|
2687
|
1 |
1 |
} else if (k < n/4) { /* k of n. Pick k with mask */ |
|
2689
|
1 |
0 |
if (n <= 32*8) mask = smask; |
|
2690
|
0 |
0 |
else Newz(0, mask, n/32 + ((n%32)?1:0), uint32_t); |
|
|
0 |
0 |
else Newz(0, mask, n/32 + ((n%32)?1:0), uint32_t); |
|
|
0 |
0 |
else Newz(0, mask, n/32 + ((n%32)?1:0), uint32_t); |
|
2691
|
4 |
1 |
for (i = 0; i < k; i++) { |
|
2694
|
0 |
4 |
} while ( mask[j>>5] & (1U << (j&0x1F)) ); |
|
2698
|
0 |
1 |
if (mask != smask) Safefree(mask); |
|
2699
|
0 |
1 |
} else if (k < n) { /* k of n. FYK shuffle n, pick k */ |
|
2701
|
0 |
0 |
New(0, T, n, UV); |
|
2702
|
0 |
0 |
for (i = 0; i < n; i++) |
|
2704
|
0 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
|
0 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
2711
|
100 |
1 |
for (i = 0; i < n; i++) |
|
2713
|
100 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
|
99 |
1 |
for (i = 0; i < k && i <= n-2; i++) { |