| line |
true |
false |
branch |
|
91
|
52549 |
5317 |
return (*x > *y) ? 1 : (*x < *y) ? -1 : 0; |
|
|
52549 |
0 |
return (*x > *y) ? 1 : (*x < *y) ? -1 : 0; |
|
148
|
12983 |
431033 |
if (n <= 10) |
|
149
|
9145 |
3838 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
|
5704 |
3441 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
|
3422 |
2282 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
|
1894 |
1528 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
151
|
429111 |
1922 |
if (n < UVCONST(200000000)) { |
|
158
|
240559 |
188552 |
if (mtab == 0) |
|
162
|
18329 |
170223 |
if (d < NPRIME_SIEVE30) |
|
163
|
4186 |
14143 |
return (prime_sieve30[d] & mtab) ? 0 : 2; |
|
165
|
141340 |
28883 |
if (!(n%7) || !(n%11) || !(n%13)) return 0; |
|
|
127598 |
13742 |
if (!(n%7) || !(n%11) || !(n%13)) return 0; |
|
|
10451 |
117147 |
if (!(n%7) || !(n%11) || !(n%13)) return 0; |
|
168
|
105267 |
11880 |
if (n <= get_prime_cache(0,0)) { |
|
170
|
105267 |
0 |
if (n <= get_prime_cache(0, &sieve)) |
|
171
|
44506 |
60761 |
isprime = 2*((sieve[d] & mtab) == 0); |
|
173
|
105267 |
0 |
if (isprime >= 0) |
|
185
|
18862 |
6270 |
if (n < 30*NPRIME_SIEVE30) { |
|
187
|
18861 |
1 |
if (next != 0) return next; |
|
190
|
0 |
6271 |
if (n >= MPU_MAX_PRIME) return 0; /* Overflow */ |
|
192
|
4068 |
2203 |
if (n < get_prime_cache(0,0)) { |
|
195
|
4068 |
0 |
next = (n < sieve_size) ? next_prime_in_sieve(sieve, n, sieve_size) : 0; |
|
197
|
4068 |
0 |
if (next != 0) return next; |
|
204
|
7524 |
2203 |
} while (!is_prob_prime(n)); |
|
213
|
20172 |
8187 |
if (n < 30*NPRIME_SIEVE30) |
|
216
|
4023 |
4164 |
if (n < get_prime_cache(0,0)) { |
|
219
|
4023 |
0 |
prev = (n < sieve_size) ? prev_prime_in_sieve(sieve, n) : 0; |
|
221
|
4023 |
0 |
if (prev != 0) return prev; |
|
228
|
10105 |
4164 |
} while (!is_prob_prime(n)); |
|
242
|
0 |
0 |
} while ((val = t)); |
|
244
|
0 |
0 |
while (--s > ptr) { char c = *s; *s = *ptr; *ptr++ = c; } |
|
249
|
0 |
0 |
if (res == -1) croak("print_primes write error"); |
|
255
|
0 |
0 |
if ((low <= 2) && (high >= 2)) bend += my_sprint(bend,2); |
|
|
0 |
0 |
if ((low <= 2) && (high >= 2)) bend += my_sprint(bend,2); |
|
256
|
0 |
0 |
if ((low <= 3) && (high >= 3)) bend += my_sprint(bend,3); |
|
|
0 |
0 |
if ((low <= 3) && (high >= 3)) bend += my_sprint(bend,3); |
|
257
|
0 |
0 |
if ((low <= 5) && (high >= 5)) bend += my_sprint(bend,5); |
|
|
0 |
0 |
if ((low <= 5) && (high >= 5)) bend += my_sprint(bend,5); |
|
258
|
0 |
0 |
if (low < 7) low = 7; |
|
260
|
0 |
0 |
if (low <= high) { |
|
264
|
0 |
0 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
265
|
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 ) |
|
267
|
0 |
0 |
if (bend-buf > 8000) { bend = write_buf(fd, buf, bend); } |
|
272
|
0 |
0 |
if (bend > buf) { bend = write_buf(fd, buf, bend); } |
|
294
|
47 |
22 |
if (sqrtn*sqrtn != hi && sqrtn < (UVCONST(1)<<(BITS_PER_WORD/2))-1) sqrtn++; |
|
|
47 |
0 |
if (sqrtn*sqrtn != hi && sqrtn < (UVCONST(1)<<(BITS_PER_WORD/2))-1) sqrtn++; |
|
297
|
34 |
35 |
if (hi < 100 || count <= 10 || (hi > (1UL<<25) && count < icbrt(hi)/4)) { |
|
|
34 |
0 |
if (hi < 100 || count <= 10 || (hi > (1UL<<25) && count < icbrt(hi)/4)) { |
|
|
0 |
34 |
if (hi < 100 || count <= 10 || (hi > (1UL<<25) && count < icbrt(hi)/4)) { |
|
|
0 |
0 |
if (hi < 100 || count <= 10 || (hi > (1UL<<25) && count < icbrt(hi)/4)) { |
|
298
|
671 |
35 |
for (i = 0; i < count; i++) |
|
304
|
34 |
0 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
102 |
336 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
68 |
34 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
34 |
34 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
29 |
307 |
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 |
336 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
34 |
404 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
306
|
77 |
327 |
if (p > nextlog) { |
|
310
|
0 |
404 |
for (i = PGTLO(p, p, lo); i >= lo && i <= hi; i += p) |
|
|
0 |
0 |
for (i = PGTLO(p, p, lo); i >= lo && i <= hi; i += p) |
|
|
146749 |
0 |
for (i = PGTLO(p, p, lo); i >= lo && i <= hi; i += p) |
|
|
146345 |
404 |
for (i = PGTLO(p, p, lo); i >= lo && i <= hi; i += p) |
|
312
|
0 |
404 |
for (i = PGTLO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
|
0 |
0 |
for (i = PGTLO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
|
37943 |
0 |
for (i = PGTLO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
|
37539 |
404 |
for (i = PGTLO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
316
|
10 |
24 |
logp = log2floor(lo); |
|
318
|
83991 |
34 |
for (i = 0; i < count; i++) { |
|
320
|
319 |
83672 |
if (i >= nextlogi) nextlogi = (UVCONST(2) << ++logp) - lo; |
|
321
|
32880 |
51111 |
if (a & 0x80) { a = 0; } |
|
322
|
12146 |
38965 |
else if (a >= logp) { a = 1 - 2*(a&1); } |
|
326
|
24 |
10 |
if (lo == 0) mu[0] = 0; |
|
337
|
0 |
8 |
if (hi < lo) croak("range_totient error hi %"UVuf" < lo %"UVuf"\n", hi, lo); |
|
338
|
0 |
8 |
New(0, totients, count, UV); |
|
341
|
2 |
6 |
if (hi < 100 || count <= 10 || hi/count > 1000) { |
|
|
2 |
0 |
if (hi < 100 || count <= 10 || hi/count > 1000) { |
|
|
0 |
2 |
if (hi < 100 || count <= 10 || hi/count > 1000) { |
|
342
|
35 |
6 |
for (i = 0; i < count; i++) |
|
347
|
0 |
2 |
if (hi == UV_MAX) { |
|
353
|
1 |
1 |
if (lo == 0) { |
|
356
|
1 |
0 |
UV max_index = (hi < 67) ? 18 |
|
|
1 |
0 |
UV max_index = (hi < 67) ? 18 |
|
361
|
0 |
1 |
New(0, prime, max_index, UV); /* could use prime_count_upper(hi) */ |
|
363
|
119 |
1 |
for (i = 2; i <= hi/2; i++) { |
|
365
|
60 |
59 |
if ( !(i&1) ) { |
|
366
|
1 |
59 |
if (i == 2) { totients[2] = 1; prime[nprimes++] = 2; } |
|
369
|
29 |
30 |
if (totients[i] == 0) { |
|
373
|
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]) { |
|
374
|
19 |
108 |
if (i % prime[j] == 0) { |
|
385
|
60 |
1 |
for (i = ((hi/2) + 1) | 1; i <= hi; i += 2) |
|
386
|
22 |
38 |
if (totients[i] == 0) |
|
393
|
25 |
1 |
for (i = 0; i < count; i++) { |
|
395
|
12 |
13 |
if (v % 2 == 0) nv -= nv/2; |
|
396
|
8 |
17 |
if (v % 3 == 0) nv -= nv/3; |
|
397
|
5 |
20 |
if (v % 5 == 0) nv -= nv/5; |
|
402
|
1 |
1 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
403
|
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 ) { |
|
404
|
2 |
130 |
for (i = PGTLO(2*p,p,lo); i >= lo && i <= hi; i += p) |
|
|
128 |
2 |
for (i = PGTLO(2*p,p,lo); i >= lo && i <= hi; i += p) |
|
|
163 |
0 |
for (i = PGTLO(2*p,p,lo); i >= lo && i <= hi; i += p) |
|
|
31 |
132 |
for (i = PGTLO(2*p,p,lo); i >= lo && i <= hi; i += p) |
|
411
|
13 |
1 |
for (i = (lo | 1) - lo; i < count; i += 2) |
|
412
|
2 |
11 |
if (totients[i] == i+lo) |
|
414
|
0 |
1 |
if (lo <= 1) totients[1-lo] = 1; |
|
430
|
1 |
44 |
if (n <= 1) return n; |
|
433
|
32 |
12 |
if (maxmu < u) maxmu = u; |
|
435
|
0 |
44 |
New(0, M, maxmu+1, short); /* Works up to maxmu < 7613644886 */ |
|
437
|
56530 |
44 |
for (j = 1; j <= maxmu; j++) |
|
440
|
56530 |
44 |
for (m = 1; m <= u; m++) { |
|
441
|
34416 |
22114 |
if (mu[m] != 0) { |
|
448
|
228923217 |
34416 |
for (nmk = 1; nmk <= last_nmk; nmk++, nmkm += m) { |
|
453
|
17157 |
17259 |
sum += (mu[m] > 0) ? -inner_sum : inner_sum; |
|
474
|
15297 |
72 |
if ((n <= 3) || (n == UV_MAX)) return 1; |
|
|
0 |
15297 |
if ((n <= 3) || (n == UV_MAX)) return 1; |
|
475
|
15 |
15282 |
if ((n & (n-1)) == 0) return ctz(n); /* powers of 2 */ |
|
|
15 |
0 |
if ((n & (n-1)) == 0) return ctz(n); /* powers of 2 */ |
|
476
|
243 |
15039 |
if (is_perfect_square(n)) return 2 * powerof(isqrt(n)); |
|
477
|
50 |
14989 |
if (is_perfect_cube(n)) return 3 * powerof(icbrt(n)); |
|
480
|
8316 |
6673 |
t = n & 511; if ((t*77855451) & (t*4598053) & 862) return 1; |
|
482
|
15 |
6658 |
if (is_perfect_fifth(n)) return 5 * powerof(rootof(n,5)); |
|
483
|
7 |
6651 |
if (is_perfect_seventh(n)) return 7 * powerof(rootof(n,7)); |
|
485
|
2032 |
4619 |
if (n > 177146 && n <= UVCONST(1977326743)) { |
|
|
1858 |
174 |
if (n > 177146 && n <= UVCONST(1977326743)) { |
|
495
|
163 |
6484 |
if (n >= UVCONST(8589934592)) { |
|
499
|
2 |
161 |
if ( (t = n %121, !((t*19706187) & (t*61524433) & 876897796)) && |
|
|
0 |
2 |
if ( (t = n %121, !((t*19706187) & (t*61524433) & 876897796)) && |
|
503
|
0 |
0 |
if (n == ipow(root,11)) return 11; |
|
505
|
26 |
137 |
if ( (t = n %131, !((t*1545928325) & (t*1355660813) & 2771533888U)) && |
|
|
2 |
24 |
if ( (t = n %131, !((t*1545928325) & (t*1355660813) & 2771533888U)) && |
|
509
|
2 |
0 |
if (n == ipow(root,13)) return 13; |
|
538
|
22 |
10426 |
if (a > 0) { |
|
539
|
22 |
0 |
if (a == 1 || n <= 1) return 1; |
|
|
3 |
19 |
if (a == 1 || n <= 1) return 1; |
|
540
|
17 |
2 |
if ((a % 2) == 0) |
|
541
|
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); |
|
542
|
2 |
0 |
if ((a % 3) == 0) |
|
543
|
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); |
|
544
|
0 |
0 |
if ((a % 5) == 0) |
|
545
|
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); |
|
548
|
0 |
10426 |
if (a != 0) return !(ret % a); /* Is the max power divisible by a? */ |
|
549
|
148 |
10278 |
return (ret == 1) ? 0 : ret; |
|
562
|
0 |
532 |
if (k == 0) return 0; |
|
563
|
46 |
486 |
if (k == 1) return n; |
|
564
|
122 |
364 |
if (k == 2) return isqrt(n); |
|
565
|
12 |
352 |
if (k == 3) return icbrt(n); |
|
568
|
350 |
2 |
max = 1 + ((k >= ROOT_MAX_3) ? 2 : root_max[k]); |
|
569
|
352 |
0 |
lo = UVCONST(1) << (log2floor(n)/k); |
|
573
|
873 |
352 |
while (lo < hi) { |
|
575
|
479 |
394 |
if (ipow(mid,k) <= n) lo = mid+1; |
|
584
|
6 |
10268 |
if (n < 2) return 0; |
|
586
|
24 |
10244 |
if (!(n&1)) { |
|
587
|
15 |
9 |
if (n & (n-1)) return 0; |
|
589
|
9 |
0 |
return ctz(n); |
|
591
|
15 |
10229 |
if ((n%3) == 0) { |
|
593
|
145 |
11 |
do { n /= 3; power++; } while (n > 1 && (n%3) == 0); |
|
|
141 |
4 |
do { n /= 3; power++; } while (n > 1 && (n%3) == 0); |
|
594
|
4 |
11 |
if (n != 1) return 0; |
|
598
|
2007 |
8222 |
if ((n%5) == 0) { |
|
599
|
2563 |
10 |
do { n /= 5; power++; } while (n > 1 && (n%5) == 0); |
|
|
566 |
1997 |
do { n /= 5; power++; } while (n > 1 && (n%5) == 0); |
|
600
|
1997 |
10 |
if (n != 1) return 0; |
|
604
|
1149 |
7073 |
if ((n%7) == 0) { |
|
605
|
1394 |
9 |
do { n /= 7; power++; } while (n > 1 && (n%7) == 0); |
|
|
254 |
1140 |
do { n /= 7; power++; } while (n > 1 && (n%7) == 0); |
|
606
|
1140 |
9 |
if (n != 1) return 0; |
|
610
|
2690 |
4383 |
if (is_prob_prime(n)) |
|
614
|
4262 |
121 |
if (power == 1) power = 0; |
|
615
|
121 |
4262 |
if (power) { |
|
617
|
103 |
18 |
if (is_prob_prime(root)) |
|
629
|
331 |
2 |
if (k < 2 || n < 2) return 0; |
|
|
8 |
323 |
if (k < 2 || n < 2) return 0; |
|
630
|
95 |
228 |
if (k == 2) return ctz(n); |
|
|
95 |
0 |
if (k == 2) return ctz(n); |
|
631
|
46 |
228 |
while ( !(n % kpower) ) { |
|
642
|
200 |
401 |
if (b == 2) |
|
643
|
200 |
0 |
return log2floor(n); |
|
644
|
0 |
401 |
if (n > UV_MAX/b) { |
|
648
|
1140 |
401 |
for (v = b; v <= n; v *= b) |
|
657
|
2 |
0 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
2 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
2 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
2 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
662
|
0 |
2 |
Newz(0, s, slen, uint32_t); |
|
663
|
17 |
2 |
for (i = 0; i < slen; i++) { /* Chunks of 8 digits */ |
|
664
|
130 |
15 |
for (j = 0, d = 0, power = 1; j < 8 && len > 0; j++, power *= 10) { |
|
|
128 |
2 |
for (j = 0, d = 0, power = 1; j < 8 && len > 0; j++, power *= 10) { |
|
666
|
0 |
128 |
if (v > 9) croak("Parameter '%s' must be a positive integer",ptr); |
|
672
|
372 |
2 |
while (slen > 1) { |
|
673
|
176 |
196 |
if (s[slen-1] & 1) count++; |
|
675
|
15 |
357 |
if (s[0] == 1) { |
|
676
|
0 |
15 |
if (--slen == 0) break; |
|
679
|
1921 |
372 |
for (i = 0; i < slen; i++) { |
|
680
|
1549 |
372 |
if ( (i+1) < slen && sptr[i] & 1 ) sptr[i+1] += 100000000; |
|
|
771 |
778 |
if ( (i+1) < slen && sptr[i] & 1 ) sptr[i+1] += 100000000; |
|
685
|
54 |
2 |
for (d = s[0]; d > 0; d >>= 1) |
|
686
|
25 |
29 |
if (d & 1) |
|
698
|
3377 |
1165 |
while (a) { |
|
699
|
3377 |
0 |
int r = padic2(a); |
|
700
|
1583 |
1794 |
if (r) { |
|
701
|
1054 |
529 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
|
789 |
265 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
|
146 |
643 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
704
|
352 |
3025 |
if (a & b & 2) s = -s; |
|
707
|
1146 |
19 |
return (b == 1) ? s : 0; |
|
712
|
1146 |
10 |
if (b & 1) return kronecker_uu_sign(a, b, 1); |
|
713
|
3 |
7 |
if (!(a&1)) return 0; |
|
715
|
6 |
1 |
r = padic2(b); |
|
716
|
7 |
0 |
if (r) { |
|
717
|
5 |
2 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
0 |
5 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
0 |
0 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
725
|
35 |
14 |
if (a >= 0) return kronecker_uu(a, b); |
|
726
|
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; |
|
728
|
12 |
0 |
r = padic2(b); |
|
729
|
2 |
10 |
if (r) { |
|
730
|
0 |
2 |
if (!(a&1)) return 0; |
|
731
|
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; |
|
735
|
8 |
4 |
if (a < 0) a += b; |
|
740
|
7 |
11 |
if (a >= 0 && b >= 0) |
|
|
0 |
7 |
if (a >= 0 && b >= 0) |
|
741
|
0 |
0 |
return (b & 1) ? kronecker_uu_sign(a, b, 1) : kronecker_uu(a,b); |
|
742
|
7 |
11 |
if (b >= 0) |
|
744
|
4 |
7 |
return kronecker_su(a, -b) * ((a < 0) ? -1 : 1); |
|
749
|
472 |
2280 |
if ( (n > 12 && sizeof(UV) <= 4) || (n > 20 && sizeof(UV) <= 8) ) return 0; |
|
750
|
13871 |
2280 |
for (i = 2; i <= n; i++) |
|
757
|
186 |
24938 |
if (k == 0) return 1; |
|
758
|
2034 |
22904 |
if (k == 1) return n; |
|
759
|
1553 |
21351 |
if (k >= n) return (k == n); |
|
760
|
10633 |
10718 |
if (k > n/2) k = n-k; |
|
761
|
197192 |
16115 |
for (d = 1; d <= k; d++) { |
|
762
|
14824 |
182368 |
if (r >= UV_MAX/n) { /* Possible overflow */ |
|
766
|
5236 |
9588 |
if (r >= UV_MAX/nr) return 0; /* Unavoidable overflow */ |
|
781
|
0 |
190 |
if (m == n) return 1; |
|
782
|
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; |
|
783
|
19 |
171 |
if (m == 1) return factorial(n); |
|
786
|
0 |
171 |
if (f1 == 0) return 0; |
|
788
|
171 |
0 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
|
0 |
171 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
791
|
171 |
0 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
|
5 |
166 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
799
|
0 |
1789 |
if (m == n) return 1; |
|
800
|
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; |
|
801
|
240 |
1549 |
if (m == 1) return 1; |
|
803
|
165 |
1384 |
if ((f = factorial(m)) == 0) return 0; |
|
804
|
6586 |
1075 |
for (j = 1; j <= (IV)m; j++) { |
|
806
|
115103 |
6277 |
for (k = 1; k <= (IV)n; k++) { |
|
807
|
115103 |
0 |
if (t == 0 || j >= IV_MAX/t) return 0; |
|
|
309 |
114794 |
if (t == 0 || j >= IV_MAX/t) return 0; |
|
810
|
2890 |
3387 |
if ((m-j) & 1) t *= -1; |
|
819
|
0 |
192 |
if (m == n) return 1; |
|
820
|
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; |
|
821
|
19 |
173 |
if (m == 1) { |
|
823
|
0 |
19 |
if (f>(UV)IV_MAX) return 0; |
|
824
|
10 |
9 |
return (n&1) ? ((IV)f) : -((IV)f); |
|
827
|
816 |
126 |
for (k = 1; k <= (IV)(n-m); k++) { |
|
831
|
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; |
|
833
|
35 |
769 |
if (s2 > IV_MAX/t) return 0; |
|
835
|
430 |
339 |
s += (k & 1) ? -t : t; |
|
842
|
96 |
590 |
if (n <= 1) return n; |
|
845
|
143 |
590 |
while ((n & 0x3) == 0) { n >>= 1; totient <<= 1; } |
|
846
|
328 |
262 |
if ((n & 0x1) == 0) { n >>= 1; } |
|
850
|
623 |
590 |
for (i = 0; i < nfacs; i++) { |
|
852
|
47 |
576 |
if (f == lastf) { totient *= f; } |
|
868
|
490 |
0 |
if (k == 0 || n <= 1) return (n == 1); |
|
|
11 |
479 |
if (k == 0 || n <= 1) return (n == 1); |
|
869
|
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; |
|
873
|
205 |
457 |
while ((n & 0x3) == 0) { n >>= 1; totient *= (1<
|
|
874
|
226 |
231 |
if ((n & 0x1) == 0) { n >>= 1; totient *= ((1<
|
|
876
|
503 |
457 |
for (i = 0; i < nfac; i++) { |
|
880
|
170 |
410 |
while (i+1 < nfac && p == factors[i+1]) { |
|
|
77 |
93 |
while (i+1 < nfac && p == factors[i+1]) { |
|
893
|
8 |
262 |
if (n < 8) return totient(n); |
|
894
|
9 |
253 |
if ((n & (n-1)) == 0) return n >> 2; |
|
896
|
253 |
0 |
i = ctz(n); |
|
897
|
95 |
158 |
if (i > 0) { |
|
899
|
20 |
75 |
lambda <<= (i>2) ? i-2 : i-1; |
|
902
|
347 |
253 |
for (i = 0; i < nfactors; i++) { |
|
904
|
141 |
253 |
while (i+1 < nfactors && p == fac[i+1]) { |
|
|
47 |
94 |
while (i+1 < nfactors && p == fac[i+1]) { |
|
919
|
19440 |
560 |
if (n < 561 || !(n&1)) return 0; |
|
|
9720 |
9720 |
if (n < 561 || !(n&1)) return 0; |
|
922
|
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)) |
|
926
|
1333 |
6678 |
if (!(n% 5) && ((n-1) % 4 != 0)) return 0; |
|
|
666 |
667 |
if (!(n% 5) && ((n-1) % 4 != 0)) return 0; |
|
927
|
918 |
6427 |
if (!(n% 7) && ((n-1) % 6 != 0)) return 0; |
|
|
574 |
344 |
if (!(n% 7) && ((n-1) % 6 != 0)) return 0; |
|
928
|
567 |
6204 |
if (!(n%11) && ((n-1) % 10 != 0)) return 0; |
|
|
438 |
129 |
if (!(n%11) && ((n-1) % 10 != 0)) return 0; |
|
929
|
451 |
5882 |
if (!(n%13) && ((n-1) % 12 != 0)) return 0; |
|
|
349 |
102 |
if (!(n%13) && ((n-1) % 12 != 0)) return 0; |
|
930
|
355 |
5629 |
if (!(n%17) && ((n-1) % 16 != 0)) return 0; |
|
|
306 |
49 |
if (!(n%17) && ((n-1) % 16 != 0)) return 0; |
|
931
|
302 |
5376 |
if (!(n%19) && ((n-1) % 18 != 0)) return 0; |
|
|
261 |
41 |
if (!(n%19) && ((n-1) % 18 != 0)) return 0; |
|
932
|
244 |
5173 |
if (!(n%23) && ((n-1) % 22 != 0)) return 0; |
|
|
220 |
24 |
if (!(n%23) && ((n-1) % 22 != 0)) return 0; |
|
935
|
0 |
5197 |
if (n > 5000000) { |
|
936
|
0 |
0 |
if (!(n%29) && ((n-1) % 28 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%29) && ((n-1) % 28 != 0)) return 0; |
|
937
|
0 |
0 |
if (!(n%31) && ((n-1) % 30 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%31) && ((n-1) % 30 != 0)) return 0; |
|
938
|
0 |
0 |
if (!(n%37) && ((n-1) % 36 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%37) && ((n-1) % 36 != 0)) return 0; |
|
939
|
0 |
0 |
if (!(n%41) && ((n-1) % 40 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%41) && ((n-1) % 40 != 0)) return 0; |
|
940
|
0 |
0 |
if (!(n%43) && ((n-1) % 42 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%43) && ((n-1) % 42 != 0)) return 0; |
|
941
|
0 |
0 |
if (!is_pseudoprime(n,2)) return 0; |
|
945
|
4664 |
533 |
if (nfactors < 3) |
|
947
|
1321 |
9 |
for (i = 0; i < nfactors; i++) { |
|
948
|
1321 |
0 |
if (exp[i] > 1 || ((n-1) % (fac[i]-1)) != 0) |
|
|
524 |
797 |
if (exp[i] > 1 || ((n-1) % (fac[i]-1)) != 0) |
|
956
|
13015 |
144 |
for (i = 0; i < nfactors; i++) { |
|
958
|
13015 |
0 |
if (d == 0 || (p % d) != 0) |
|
|
8086 |
4929 |
if (d == 0 || (p % d) != 0) |
|
970
|
68 |
5334 |
if (n < 35) return 0; |
|
973
|
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)) |
|
978
|
741 |
2552 |
if (nfactors < 2) |
|
981
|
6371 |
2518 |
for (i = 0; i < nfactors; i++) |
|
982
|
34 |
6337 |
if (exp[i] > 1) |
|
990
|
1448 |
1070 |
if (nfactors == 2) { |
|
992
|
5953 |
0 |
for (i = 0; i < (int)ndivisors; i++) { |
|
995
|
1448 |
4505 |
if (d >= spf) break; |
|
996
|
92 |
4413 |
if (is_quasi_base(nfactors, fac, n-k, k)) |
|
1001
|
8453 |
1070 |
for (i = 0; i < (int)ndivisors; i++) { |
|
1004
|
3693 |
4760 |
if (lpf > d && k >= spf) continue; |
|
|
3658 |
35 |
if (lpf > d && k >= spf) continue; |
|
1005
|
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)) |
|
1016
|
12 |
80256 |
if (n < 6) return (n == 4); |
|
1017
|
39798 |
40458 |
if (!(n&1)) return !!is_prob_prime(n>>1); |
|
1018
|
13410 |
27048 |
if (!(n%3)) return !!is_prob_prime(n/3); |
|
1019
|
5361 |
21687 |
if (!(n%5)) return !!is_prob_prime(n/5); |
|
1022
|
87127 |
36 |
for (sp = 4; sp < 60; sp++) { |
|
1024
|
15103 |
72024 |
if (p > n3) |
|
1026
|
6548 |
65476 |
if ((n % p) == 0) |
|
1030
|
15105 |
34 |
if (is_def_prime(n)) return 0; |
|
|
9919 |
5220 |
if (is_def_prime(n)) return 0; |
|
1031
|
5195 |
25 |
if (p > n3) return 1; /* past this, n is a composite and larger than p^3 */ |
|
1033
|
0 |
25 |
if (factor_one(n, factors, 0, 0) != 2) return 0; |
|
1034
|
25 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
25 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
0 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
24 |
1 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
20 |
4 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
1 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
1039
|
94 |
8 |
if (r) { |
|
1040
|
47 |
47 |
if (!neg) { |
|
1042
|
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); |
|
1048
|
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); |
|
1061
|
206 |
255 |
if (n & 1) return 0; |
|
1063
|
6 |
249 |
if (n == 1) return 1; |
|
1064
|
75 |
174 |
if (n < maxd && is_prime(2*n+1)) return 1; |
|
|
19 |
56 |
if (n < maxd && is_prime(2*n+1)) return 1; |
|
1067
|
1045 |
41 |
for (i = 0, res = 0; i < ndivisors && divs[i] < maxd && res == 0; i++) { |
|
|
871 |
174 |
for (i = 0, res = 0; i < ndivisors && divs[i] < maxd && res == 0; i++) { |
|
|
856 |
15 |
for (i = 0, res = 0; i < ndivisors && divs[i] < maxd && res == 0; i++) { |
|
1069
|
507 |
349 |
if (!is_prime(p)) continue; |
|
1072
|
398 |
3 |
if (r == p || _totpred(r, d)) { res = 1; break; } |
|
|
13 |
385 |
if (r == p || _totpred(r, d)) { res = 1; break; } |
|
1073
|
333 |
52 |
if (r % p) break; |
|
1082
|
123 |
1 |
return (n == 0 || (n & 1)) ? (n==1) : _totpred(n,n); |
|
|
60 |
63 |
return (n == 0 || (n & 1)) ? (n==1) : _totpred(n,n); |
|
1091
|
1 |
102 |
if (n == 1) return 2; |
|
1092
|
101 |
1 |
if (n < 1 || n & 1) return 0; |
|
|
49 |
52 |
if (n < 1 || n & 1) return 0; |
|
1093
|
15 |
37 |
if (is_prime(n >> 1)) { /* Coleman Remark 3.3 (Thm 3.1) and Prop 6.2 */ |
|
1094
|
8 |
7 |
if (!is_prime(n+1)) return 0; |
|
1095
|
5 |
2 |
if (n >= 10) return 2; |
|
1104
|
463 |
39 |
for (i = 0; i < ndivisors; i++) { |
|
1106
|
245 |
218 |
if (is_prime(p)) { |
|
1109
|
381 |
245 |
for (j = 0; j <= v; j++) { |
|
1111
|
39 |
342 |
if (np == 1) { |
|
1115
|
8912 |
0 |
for (k = 0; k < ndivisors && divs[k] <= ndiv; k++) { |
|
|
8570 |
342 |
for (k = 0; k < ndivisors && divs[k] <= ndiv; k++) { |
|
1117
|
4492 |
4078 |
if ((ndiv % d2) != 0) continue; |
|
1119
|
1896 |
2182 |
if (val > 0) { |
|
1143
|
0 |
2 |
MPUassert(n <= UV_MAX/7.5, "inverse_totient_list n too large"); |
|
1145
|
0 |
2 |
if (n == 1) { |
|
1151
|
2 |
0 |
if (n < 1 || n & 1) { |
|
|
0 |
2 |
if (n < 1 || n & 1) { |
|
1155
|
0 |
2 |
if (is_prime(n >> 1)) { /* Coleman Remark 3.3 (Thm 3.1) and Prop 6.2 */ |
|
1156
|
0 |
0 |
if (!is_prime(n+1)) { |
|
1160
|
0 |
0 |
if (n >= 10) { |
|
1173
|
72 |
2 |
for (i = 0; i < ndivisors; i++) { |
|
1175
|
23 |
49 |
if (is_prime(p)) { |
|
1178
|
33 |
23 |
for (j = 0; j <= v; j++) { |
|
1180
|
2 |
31 |
if (dp == 1) { |
|
1183
|
888 |
0 |
for (k = 0; k < ndivisors && divs[k] <= ndiv; k++) { |
|
|
857 |
31 |
for (k = 0; k < ndivisors && divs[k] <= ndiv; k++) { |
|
1185
|
451 |
406 |
if ((ndiv % d2) != 0) continue; |
|
1187
|
93 |
313 |
if (vals != 0) |
|
1200
|
2 |
0 |
if (tlist != 0 && *ntotients > 0) { |
|
|
2 |
0 |
if (tlist != 0 && *ntotients > 0) { |
|
1201
|
0 |
2 |
New(0, totlist, *ntotients, UV); |
|
1212
|
1 |
992 |
if (n == 0) return 0; |
|
1213
|
104011 |
90 |
for (v = 8, fac = 5040 % n; v < n-1 && fac != 0; v++) { |
|
|
103194 |
817 |
for (v = 8, fac = 5040 % n; v < n-1 && fac != 0; v++) { |
|
1214
|
103194 |
0 |
fac = (n < HALF_WORD) ? (fac*v) % n : mulmod(fac,v,n); |
|
1215
|
115 |
103079 |
if (fac == n-1 && (n % v) != 1) |
|
|
85 |
30 |
if (fac == n-1 && (n % v) != 1) |
|
1226
|
876 |
28856 |
if (n <= 5) return (n == 1) ? 1 : (n % 4) ? -1 : 0; |
|
|
583 |
293 |
if (n <= 5) return (n == 1) ? 1 : (n % 4) ? -1 : 0; |
|
|
442 |
141 |
if (n <= 5) return (n == 1) ? 1 : (n % 4) ? -1 : 0; |
|
1227
|
27035 |
1821 |
if (n >= 49 && (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49))) |
|
|
20280 |
6755 |
if (n >= 49 && (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49))) |
|
|
18020 |
2260 |
if (n >= 49 && (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49))) |
|
|
17292 |
728 |
if (n >= 49 && (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49))) |
|
|
368 |
16924 |
if (n >= 49 && (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49))) |
|
1229
|
15296 |
3449 |
if (n >= 361 && (!(n % 121) || !(n % 169) || !(n % 289) || !(n % 361))) |
|
|
15168 |
128 |
if (n >= 361 && (!(n % 121) || !(n % 169) || !(n % 289) || !(n % 361))) |
|
|
15078 |
90 |
if (n >= 361 && (!(n % 121) || !(n % 169) || !(n % 289) || !(n % 361))) |
|
|
15023 |
55 |
if (n >= 361 && (!(n % 121) || !(n % 169) || !(n % 289) || !(n % 361))) |
|
|
49 |
14974 |
if (n >= 361 && (!(n % 121) || !(n % 169) || !(n % 289) || !(n % 361))) |
|
1231
|
12677 |
5746 |
if (n >= 961 && (!(n % 529) || !(n % 841) || !(n % 961))) |
|
|
12649 |
28 |
if (n >= 961 && (!(n % 529) || !(n % 841) || !(n % 961))) |
|
|
12634 |
15 |
if (n >= 961 && (!(n % 529) || !(n % 841) || !(n % 961))) |
|
|
20 |
12614 |
if (n >= 961 && (!(n % 529) || !(n % 841) || !(n % 961))) |
|
1235
|
21038 |
17599 |
for (i = 1; i < nfactors; i++) |
|
1236
|
761 |
20277 |
if (factors[i] == factors[i-1]) |
|
1238
|
8865 |
8734 |
return (nfactors % 2) ? -1 : 1; |
|
1243
|
6 |
14 |
if (!primepower(n,&p)) return 1; /* Not a prime power */ |
|
1254
|
6 |
69 |
if (n <= 1) return n; /* znorder(x,0) = 0, znorder(x,1) = 1 */ |
|
1255
|
3 |
66 |
if (a <= 1) return a; /* znorder(0,x) = 0, znorder(1,x) = 1 (x > 1) */ |
|
1256
|
6 |
60 |
if (gcd_ui(a,n) > 1) return 0; |
|
1263
|
54 |
6 |
if (n & 1) { |
|
1266
|
212 |
54 |
for (i = 0; i < nfactors; i++) { |
|
1271
|
161 |
212 |
for (ek = 0; a1 != mont1 && ek++ <= ei; a1 = mont_powmod(a1, pi, n)) |
|
|
161 |
0 |
for (ek = 0; a1 != mont1 && ek++ <= ei; a1 = mont_powmod(a1, pi, n)) |
|
1273
|
0 |
212 |
if (ek > ei) return 0; |
|
1277
|
7 |
6 |
for (i = 0; i < nfactors; i++) { |
|
1282
|
7 |
7 |
for (ek = 0; a1 != 1 && ek++ <= ei; a1 = powmod(a1, pi, n)) |
|
|
7 |
0 |
for (ek = 0; a1 != 1 && ek++ <= ei; a1 = powmod(a1, pi, n)) |
|
1284
|
0 |
7 |
if (ek > ei) return 0; |
|
1295
|
5 |
20 |
if (n <= 4) return (n == 0) ? 0 : n-1; |
|
|
4 |
1 |
if (n <= 4) return (n == 0) ? 0 : n-1; |
|
1296
|
1 |
19 |
if (n % 4 == 0) return 0; |
|
1298
|
3 |
16 |
on = (n&1) ? n : (n>>1); |
|
1301
|
2 |
17 |
if (!is_prob_prime(r)) return 0; /* c^a or 2c^a */ |
|
1305
|
66 |
17 |
for (i = 0; i < nfactors; i++) |
|
1309
|
14 |
3 |
if (n & 1) { |
|
1311
|
834 |
0 |
for (a = 2; a < n; a++) { |
|
1312
|
825 |
9 |
if (a == 4 || a == 8 || a == 9) continue; /* Skip some perfect powers */ |
|
|
819 |
6 |
if (a == 4 || a == 8 || a == 9) continue; /* Skip some perfect powers */ |
|
|
6 |
813 |
if (a == 4 || a == 8 || a == 9) continue; /* Skip some perfect powers */ |
|
1314
|
812 |
1 |
if (phi == n-1) { if (kronecker_uu(a, n) != -1) continue; } |
|
|
653 |
159 |
if (phi == n-1) { if (kronecker_uu(a, n) != -1) continue; } |
|
1315
|
0 |
1 |
else { if (gcd_ui(a,n) != 1) continue; } |
|
1317
|
422 |
14 |
for (i = 0; i < nfactors; i++) |
|
1318
|
146 |
276 |
if (mont_powmod(r, phi_div_fac[i], n) == mont1) |
|
1320
|
14 |
146 |
if (i == nfactors) return a; |
|
1324
|
36 |
0 |
for (a = 2; a < n; a++) { |
|
1325
|
34 |
2 |
if (a == 4 || a == 8 || a == 9) continue; /* Skip some perfect powers */ |
|
|
33 |
1 |
if (a == 4 || a == 8 || a == 9) continue; /* Skip some perfect powers */ |
|
|
1 |
32 |
if (a == 4 || a == 8 || a == 9) continue; /* Skip some perfect powers */ |
|
1327
|
0 |
32 |
if (phi == n-1) { if (kronecker_uu(a, n) != -1) continue; } |
|
|
0 |
0 |
if (phi == n-1) { if (kronecker_uu(a, n) != -1) continue; } |
|
1328
|
16 |
16 |
else { if (gcd_ui(a,n) != 1) continue; } |
|
1329
|
20 |
3 |
for (i = 0; i < nfactors; i++) |
|
1330
|
13 |
7 |
if (powmod(a, phi_div_fac[i], n) == 1) |
|
1332
|
3 |
13 |
if (i == nfactors) return a; |
|
1341
|
2 |
45 |
if (n <= 1) return n; |
|
1342
|
20 |
25 |
if (a >= n) a %= n; |
|
1343
|
7 |
38 |
if (n <= 4) return a == n-1; |
|
1344
|
1 |
37 |
if (n % 4 == 0) return 0; |
|
1351
|
1 |
36 |
if (gcd_ui(a,n) != 1) return 0; |
|
1352
|
15 |
21 |
if (nprime) { |
|
1355
|
3 |
18 |
UV on = (n&1) ? n : (n>>1); |
|
1358
|
2 |
19 |
if (!is_prob_prime(r)) return 0; /* c^a or 2c^a */ |
|
1361
|
30 |
4 |
if (s == n-1 && kronecker_uu(a,n) != -1) return 0; |
|
|
8 |
22 |
if (s == n-1 && kronecker_uu(a,n) != -1) return 0; |
|
1365
|
1 |
25 |
if (i > 1 && gcd_ui(i, s) != 1) return 0; |
|
|
0 |
1 |
if (i > 1 && gcd_ui(i, s) != 1) return 0; |
|
1368
|
23 |
3 |
if (n & 1) { |
|
1372
|
23 |
0 |
if ((s % 2) == 0 && mont_powmod(a, s/2, n) == mont1) return 0; |
|
|
0 |
23 |
if ((s % 2) == 0 && mont_powmod(a, s/2, n) == mont1) return 0; |
|
1373
|
10 |
13 |
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; |
|
1374
|
13 |
9 |
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; |
|
1376
|
75 |
22 |
for (i = 0; i < nfacs; i++) |
|
1377
|
31 |
44 |
if (fac[i] > 5 && mont_powmod(a, s/fac[i], n) == mont1) |
|
|
0 |
31 |
if (fac[i] > 5 && mont_powmod(a, s/fac[i], n) == mont1) |
|
1383
|
3 |
0 |
if ((s % 2) == 0 && powmod(a, s/2, n) == 1) return 0; |
|
|
0 |
3 |
if ((s % 2) == 0 && powmod(a, s/2, n) == 1) return 0; |
|
1384
|
0 |
3 |
if ((s % 3) == 0 && powmod(a, s/3, n) == 1) return 0; |
|
|
0 |
0 |
if ((s % 3) == 0 && powmod(a, s/3, n) == 1) return 0; |
|
1385
|
1 |
2 |
if ((s % 5) == 0 && powmod(a, s/5, n) == 1) return 0; |
|
|
1 |
0 |
if ((s % 5) == 0 && powmod(a, s/5, n) == 1) return 0; |
|
1388
|
2 |
2 |
for (i = 0; i < nfacs; i++) |
|
1389
|
0 |
2 |
if (fac[i] > 5 && powmod(a, s/fac[i], n) == 1) |
|
|
0 |
0 |
if (fac[i] > 5 && powmod(a, s/fac[i], n) == 1) |
|
1399
|
3 |
47 |
if (a == 0 && b == 0) { os = 0; t = 0; } |
|
|
1 |
2 |
if (a == 0 && b == 0) { os = 0; t = 0; } |
|
1400
|
285 |
50 |
while (r != 0) { |
|
1406
|
4 |
46 |
if (or < 0) /* correct sign */ |
|
1408
|
50 |
0 |
if (u != 0) *u = os; |
|
1409
|
50 |
0 |
if (v != 0) *v = ot; |
|
1410
|
38 |
12 |
if (cs != 0) *cs = s; |
|
1411
|
38 |
12 |
if (ct != 0) *ct = t; |
|
1419
|
3672 |
161 |
while (nr != 0) { |
|
1424
|
41 |
120 |
if (r > 1) return 0; /* No inverse */ |
|
1425
|
68 |
52 |
if (t < 0) t += n; |
|
1431
|
0 |
2 |
if (binv == 0) return 0; |
|
1437
|
183499 |
183072 |
do { d /= p; e += d; } while (d > 0); |
|
1444
|
821 |
0 |
if (n >= m || m == 1) return 0; |
|
|
1 |
820 |
if (n >= m || m == 1) return 0; |
|
1446
|
384 |
436 |
if (n <= 10) { /* Keep things simple for small n */ |
|
1447
|
1358 |
314 |
for (i = 2; i <= n && res != 0; i++) |
|
|
1288 |
70 |
for (i = 2; i <= n && res != 0; i++) |
|
1452
|
335 |
101 |
if (n > m/2 && is_prime(m)) /* Check if we can go backwards */ |
|
|
74 |
261 |
if (n > m/2 && is_prime(m)) /* Check if we can go backwards */ |
|
1454
|
14 |
422 |
if (d < 2) |
|
1455
|
7 |
7 |
return (d == 0) ? m-1 : 1; /* Wilson's Theorem: n = m-1 and n = m-2 */ |
|
1457
|
362 |
60 |
if (d == n && d > 5000000) { /* Check for composite m that leads to 0 */ |
|
|
1 |
361 |
if (d == n && d > 5000000) { /* Check for composite m that leads to 0 */ |
|
1460
|
1 |
1 |
for (j = 0; j < nfacs; j++) { |
|
1462
|
2 |
1 |
for (k = 1; (UV)k < exp[j]; k++) |
|
1464
|
0 |
1 |
if (n >= t) return 0; |
|
1469
|
197 |
225 |
if (m & 1 && d < 40000) { |
|
|
196 |
1 |
if (m & 1 && d < 40000) { |
|
1473
|
1746 |
82 |
for (i = 2; i <= d && res != 0; i++) { |
|
|
1632 |
114 |
for (i = 2; i <= d && res != 0; i++) { |
|
1475
|
0 |
1632 |
res = mont_mulmod(res,monti,m); |
|
1477
|
0 |
196 |
res = mont_recover(res, m); |
|
1480
|
225 |
1 |
if (d < 10000) { |
|
1481
|
2011 |
20 |
for (i = 2; i <= d && res != 0; i++) |
|
|
1806 |
205 |
for (i = 2; i <= d && res != 0; i++) |
|
1494
|
3 |
1 |
for (i = 1; i <= 3; i++) /* Handle 2,3,5 assume d>10*/ |
|
1496
|
7 |
0 |
while (res != 0 && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
|
6 |
1 |
while (res != 0 && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
1497
|
348511 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
1 |
348510 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
348510 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
348511 |
20833 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
20834 |
6 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
1498
|
183069 |
165441 |
UV k = (p > (d>>1)) ? p : _powfactor(p, d, m); |
|
1500
|
0 |
348510 |
if (res == 0) break; |
|
1507
|
60 |
362 |
if (d != n && res != 0) { /* Handle backwards case */ |
|
|
60 |
0 |
if (d != n && res != 0) { /* Handle backwards case */ |
|
1508
|
31 |
29 |
if (!(d&1)) res = submod(m,res,m); |
|
1516
|
8 |
7 |
if (p-s < s) s = p-s; |
|
1517
|
0 |
15 |
if (mulmod(s, s, p) != a) return 0; |
|
1591
|
1 |
7 |
if ((p % 4) == 3) { |
|
1593
|
0 |
1 |
return mont_recover(b, p); |
|
1596
|
5 |
2 |
if ((p % 8) == 5) { /* Atkin's algorithm. Faster than Legendre. */ |
|
1600
|
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); |
|
1602
|
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); |
|
1603
|
0 |
5 |
return mont_recover(b, p); |
|
1605
|
1 |
1 |
if ((p % 16) == 9) { /* Müller's algorithm extending Atkin */ |
|
1609
|
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); |
|
1610
|
0 |
1 |
if (mont_sqrmod(beta,p) != submod(0,mont1,p)) { |
|
|
1 |
0 |
if (mont_sqrmod(beta,p) != submod(0,mont1,p)) { |
|
1611
|
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); |
|
1613
|
0 |
1 |
alpha = mont_mulmod(alpha, mont_powmod(d,(p-9)>>3,p), p); |
|
1614
|
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); |
|
1615
|
0 |
1 |
beta = mont_mulmod(submod(beta,mont1,p), d, p); |
|
1619
|
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); |
|
1620
|
0 |
1 |
return mont_recover(b, p); |
|
1624
|
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; |
|
1632
|
0 |
1 |
while (kronecker_uu(t, p) != -1) { |
|
1634
|
0 |
0 |
if (t == 201) { /* exit if p looks like a composite */ |
|
1635
|
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) |
|
1637
|
0 |
0 |
} else if (t >= 20000) { /* should never happen */ |
|
1647
|
2 |
1 |
while (b != mont1) { |
|
1649
|
5 |
0 |
for (m = 0; m < r && t != mont1; m++) |
|
|
3 |
2 |
for (m = 0; m < r && t != mont1; m++) |
|
1650
|
0 |
3 |
t = mont_sqrmod(t, p); |
|
1651
|
0 |
2 |
if (m >= r) break; |
|
1653
|
0 |
2 |
x = mont_mulmod(x, t, p); |
|
1654
|
0 |
2 |
z = mont_mulmod(t, t, p); |
|
1655
|
0 |
2 |
b = mont_mulmod(b, z, p); |
|
1658
|
0 |
1 |
return mont_recover(x, p); |
|
1665
|
0 |
10 |
if (p == 0) return 0; |
|
1666
|
2 |
8 |
if (a >= p) a %= p; |
|
1667
|
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); |
|
1679
|
2 |
5 |
if (n == 0) return 0; |
|
1680
|
0 |
5 |
if (a >= n) a %= n; |
|
1681
|
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); |
|
1684
|
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; |
|
1687
|
0 |
3 |
if ((n % 4) == 0) { |
|
1688
|
0 |
0 |
if ((n % 8) == 0) { |
|
1689
|
0 |
0 |
if ((a % 8) != 1) return 0; |
|
1691
|
0 |
0 |
if ((a % 4) != 1) return 0; |
|
1697
|
0 |
3 |
if (gcdan == 1) { |
|
1698
|
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; |
|
1699
|
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; |
|
1700
|
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; |
|
1707
|
0 |
3 |
if (gcdan == 1) { |
|
1708
|
0 |
0 |
for (i = 0; i < nfactors; i++) |
|
1709
|
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; |
|
1712
|
8 |
3 |
for (i = 0; i < nfactors; i++) { |
|
1715
|
3 |
5 |
if (fac[i] == 2) { |
|
1716
|
3 |
0 |
if (exp[i] == 1) { |
|
1718
|
0 |
0 |
} else if (exp[i] == 2) { |
|
1725
|
0 |
0 |
for (j = 2; j < exp[i]; j++) { |
|
1728
|
0 |
0 |
for (k = 0; k < nthis && nnext < 254; k++) { |
|
|
0 |
0 |
for (k = 0; k < nthis && nnext < 254; k++) { |
|
1730
|
0 |
0 |
if (sqrmod(r,p) == (a % p)) |
|
1732
|
0 |
0 |
if (sqrmod(p-r,p) == (a % p)) |
|
1735
|
0 |
0 |
if (nnext == 0) return 0; |
|
1738
|
0 |
0 |
for (k = 0; k < nnext; k++) |
|
1748
|
0 |
5 |
if (!sqrtmod(&(sqr[i]), a, p)) |
|
1752
|
0 |
5 |
for (j = 1; j < exp[i]; j++) { |
|
1759
|
0 |
0 |
if (expect != 1 || sqrmod(sol,p) != (a % p)) { |
|
|
0 |
0 |
if (expect != 1 || sqrmod(sol,p) != (a % p)) { |
|
1768
|
8 |
3 |
for (i = 0; i < nfactors; i++) |
|
1772
|
3 |
0 |
return (i == 1) ? verify_sqrtmod(p, s, a, n) : 0; |
|
1781
|
0 |
4 |
if (num == 0) return 0; |
|
1783
|
8 |
0 |
for (i = 0; i < num; i++) { |
|
1786
|
3 |
5 |
if (gcd != 1) return 0; /* not coprime */ |
|
1788
|
1 |
4 |
if (ni > (UV_MAX/lcm)) return 0; /* lcm overflow */ |
|
1791
|
0 |
0 |
for (i = 0; i < num; i++) { |
|
1795
|
0 |
0 |
if (inverse == 0) return 0; /* n's coprime so should never happen */ |
|
1808
|
1 |
29 |
if (num == 0) return 0; |
|
1811
|
319 |
29 |
for (gi = 0, gap = sgaps[gi]; gap >= 1; gap = sgaps[++gi]) { |
|
1812
|
42 |
319 |
for (i = gap; i < num; i++) { |
|
1814
|
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) |
|
1820
|
1 |
28 |
if (n[0] > IV_MAX) return _simple_chinese(a,n,num,status); |
|
1822
|
38 |
20 |
for (i = 1; i < num; i++) { |
|
1826
|
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; } |
|
1827
|
18 |
15 |
if (s < 0) s = -s; |
|
1828
|
15 |
18 |
if (t < 0) t = -t; |
|
1829
|
3 |
30 |
if (s > (IV)(IV_MAX/lcm)) return _simple_chinese(a,n,num,status); |
|
1831
|
14 |
16 |
if (u < 0) u += lcm; |
|
1832
|
15 |
15 |
if (v < 0) v += lcm; |
|
1845
|
8 |
1 |
for (k = log2floor(n); k > 0; k--) { |
|
|
49 |
9 |
for (k = log2floor(n); k > 0; k--) { |
|
1990
|
53 |
5 |
if (n < 500) { |
|
1991
|
326 |
53 |
for (i = 1; (tp = primes_tiny[i]) <= n; i++) { |
|
1998
|
0 |
5 |
if (n >= _cheby_theta[0].n) { |
|
1999
|
0 |
0 |
for (i = 1; i < NCHEBY_VALS; i++) |
|
2000
|
0 |
0 |
if (n < _cheby_theta[i].n) |
|
2020
|
7 |
5 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
2021
|
214098 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
5 |
214093 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
214078 |
15 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
214098 |
11320 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
11325 |
7 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
2023
|
26758 |
187320 |
if (++i >= (LNV_IS_QUAD ? 64 : 8)) { |
|
2030
|
5 |
0 |
if (prod > 1.0) { KAHAN_SUM(sum, loglnv(prod)); prod = LNV_ONE; } |
|
2034
|
0 |
5 |
if (initial_sum > 0) KAHAN_SUM(sum, initial_sum); |
|
2068
|
0 |
234 |
if (x == 0) croak("Invalid input to ExponentialIntegral: x must be != 0"); |
|
2070
|
0 |
234 |
if (x >= 12000) return INFINITY; |
|
2071
|
0 |
234 |
if (x <= -12000) return 0; |
|
2073
|
1 |
233 |
if (x < -1) { |
|
2078
|
20 |
0 |
for (n = 1; n <= 100000; n++) { |
|
2086
|
1 |
19 |
if ( fabslnv(val-old) <= LNV_EPSILON*fabslnv(val) ) |
|
2089
|
5 |
228 |
} else if (x < 0) { |
|
2108
|
228 |
0 |
} else if (x < (-2 * loglnv(LNV_EPSILON))) { |
|
2111
|
15320 |
0 |
for (n = 2; n <= 200; n++) { |
|
2117
|
228 |
15092 |
if (term < LNV_EPSILON*sum) break; |
|
2123
|
0 |
0 |
} else if (x >= 24) { |
|
2147
|
0 |
0 |
for (n = 0; n <= 8; n++) |
|
2155
|
0 |
0 |
for (n = 1; n <= 200; n++) { |
|
2158
|
0 |
0 |
if (term < LNV_EPSILON*sum) break; |
|
2159
|
0 |
0 |
if (term < last_term) { |
|
2176
|
0 |
2227 |
if (x == 0) return 0; |
|
2177
|
0 |
2227 |
if (x == 1) return -INFINITY; |
|
2178
|
0 |
2227 |
if (x == 2) return li2; |
|
2179
|
0 |
2227 |
if (x < 0) croak("Invalid input to LogarithmicIntegral: x must be >= 0"); |
|
2180
|
0 |
2227 |
if (x >= NV_MAX) return INFINITY; |
|
2183
|
2227 |
0 |
if (x > 1) { |
|
2189
|
89801 |
0 |
for (n = 1, k = 0; n < 200; n++) { |
|
2194
|
45548 |
89801 |
for (; k <= (n - 1) / 2; k++) |
|
2198
|
2227 |
87574 |
if (fabslnv(sum - old_sum) <= LNV_EPSILON) break; |
|
2210
|
0 |
94 |
t = (lx <= 2) ? 2 : lx * logl(lx); |
|
2211
|
376 |
48 |
for (i = 0; i < 4; i++) { |
|
2214
|
282 |
94 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
|
46 |
236 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
2225
|
3 |
94 |
if (x <= 2) return x + (x > 0); |
|
2228
|
0 |
94 |
i = (x > 4e16) ? 2048 : 128; |
|
2229
|
0 |
94 |
if (Li(r-1) >= lx) { |
|
2230
|
0 |
0 |
while (Li(r-i) >= lx) r -= i; |
|
2231
|
0 |
0 |
for (i = i/2; i > 0; i /= 2) |
|
2232
|
0 |
0 |
if (Li(r-i) >= lx) r -= i; |
|
2234
|
0 |
94 |
while (Li(r+i-1) < lx) r += i; |
|
2235
|
658 |
94 |
for (i = i/2; i > 0; i /= 2) |
|
2236
|
0 |
658 |
if (Li(r+i-1) < lx) r += i; |
|
2246
|
0 |
23 |
if (lx <= 3.5) { |
|
2250
|
0 |
23 |
if (lx < 50) { t *= 1.2; } |
|
2251
|
1 |
22 |
else if (lx < 1000) { t *= 1.15; } |
|
2259
|
116 |
0 |
for (i = 0; i < 100; i++) { |
|
2272
|
93 |
23 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
|
23 |
70 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
2280
|
0 |
23 |
if (x < 2) return x + (x > 0); |
|
2366
|
0 |
3049 |
if (x < 0) croak("Invalid input to RiemannZeta: x must be >= 0"); |
|
2367
|
0 |
3049 |
if (x == 1) return INFINITY; |
|
2369
|
3045 |
4 |
if (x == (unsigned int)x) { |
|
2371
|
3045 |
0 |
if ((k >= 0) && (k < (int)NPRECALC_ZETA)) |
|
|
2 |
3043 |
if ((k >= 0) && (k < (int)NPRECALC_ZETA)) |
|
2376
|
3047 |
0 |
if (x >= 0.5 && x <= 5.0) { |
|
|
2 |
3045 |
if (x >= 0.5 && x <= 5.0) { |
|
2401
|
0 |
3045 |
if (x > 17000.0) |
|
2447
|
9776 |
2 |
for (i = 2; i < 11; i++) { |
|
2450
|
3043 |
6733 |
if (fabsl(b) < fabsl(LDBL_EPSILON * s)) |
|
2455
|
19 |
0 |
for (i = 0; i < 13; i++) { |
|
2461
|
2 |
17 |
if (fabsl(t) < fabsl(LDBL_EPSILON * s)) |
|
2475
|
0 |
150 |
if (x <= 0) croak("Invalid input to RiemannR: x must be > 0"); |
|
2477
|
2 |
148 |
if (x > 1e19) { |
|
2480
|
132 |
0 |
for (k = 2; k <= 100; k++) { |
|
2481
|
50 |
82 |
if (amob[k] == 0) continue; |
|
2484
|
0 |
82 |
if (part_term > LDBL_MAX) return INFINITY; |
|
2488
|
2 |
80 |
if (fabsl(sum - old_sum) <= LDBL_EPSILON) break; |
|
2498
|
10829 |
0 |
for (k = 1; k <= 10000; k++) { |
|
2499
|
7786 |
3043 |
ki = (k-1 < NPRECALC_ZETA) ? riemann_zeta_table[k-1] : ld_riemann_zeta(k+1); |
|
2505
|
148 |
10681 |
if (fabsl(sum - old_sum) <= LDBL_EPSILON) break; |
|
2513
|
2 |
6 |
if (x < -0.060) { /* Pade(3,2) */ |
|
2515
|
0 |
2 |
long double t = (ti <= 0.0L) ? 0.0L : sqrtl(ti); |
|
2519
|
2 |
4 |
} else if (x < 1.363) { /* Winitzki 2003 section 3.5 */ |
|
2522
|
0 |
4 |
} else if (x < 3.7) { /* Modification of Vargas 2013 */ |
|
2545
|
0 |
9 |
if (x < -0.36787944117145L) |
|
2547
|
1 |
8 |
if (x == 0.0L) return 0.0L; |
|
2552
|
0 |
8 |
if (w <= -1.0L) return -1.0L + 8*LDBL_EPSILON; |
|
2554
|
1 |
7 |
if (x < -0.36783) return w; |
|
2568
|
28 |
2 |
for (i = 0; i < 6 && w != 0.0L; i++) { |
|
|
28 |
0 |
for (i = 0; i < 6 && w != 0.0L; i++) { |
|
2576
|
5 |
23 |
if (fabsl(wen) <= 64*LDBL_EPSILON) break; |
|
2608
|
0 |
987 |
if (digits <= 0) return 0; |
|
2609
|
15 |
972 |
if (digits <= DBL_DIG && digits <= 18) { |
|
|
15 |
0 |
if (digits <= DBL_DIG && digits <= 18) { |
|
2618
|
0 |
972 |
New(0, a, c, uint32_t); |
|
2619
|
1776026 |
972 |
for (b = 0; b < c; b++) a[b] = 2000; |
|
2622
|
125887 |
729 |
while ((b = c -= 14) > 0 && i < (uint32_t)digits) { |
|
|
125644 |
243 |
while ((b = c -= 14) > 0 && i < (uint32_t)digits) { |
|
2624
|
0 |
125644 |
if (b > 107000) { /* Use 64-bit intermediate while necessary. */ |
|
2625
|
0 |
0 |
for (d64 = d; --b > 107000; ) { |
|
2634
|
148341500 |
125644 |
while (--b > 0) { |
|
2642
|
0 |
125644 |
if (d4 > 9999) { |
|
2645
|
0 |
0 |
for (b=i-1; out[b] == '0'+1; b--) { out[b]='0'; out[b-1]++; } |
|
2654
|
480 |
492 |
if (out[digits-1] >= '5') out[digits-2]++; /* Round */ |
|
2655
|
70 |
972 |
for (i = digits-2; out[i] == '9'+1; i--) /* Keep rounding */ |
|
2672
|
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"); |
|
2674
|
4 |
0 |
if (b[0] == '-' || b[0] == '+') { b++; blen--; } |
|
|
0 |
4 |
if (b[0] == '-' || b[0] == '+') { b++; blen--; } |
|
2675
|
4 |
0 |
while (blen > 0 && *b == '0') { b++; blen--; } |
|
|
0 |
4 |
while (blen > 0 && *b == '0') { b++; blen--; } |
|
2676
|
80 |
4 |
for (i = 0; i < blen; i++) |
|
2677
|
0 |
80 |
if (!isDIGIT(b[i])) |
|
2679
|
4 |
0 |
if (blen == 0 || i < blen) |
|
|
0 |
4 |
if (blen == 0 || i < blen) |
|
2682
|
2 |
2 |
if (a == 0) return 1; |
|
2685
|
2 |
0 |
if (a[0] == '-' || a[0] == '+') { a++; alen--; } |
|
|
0 |
2 |
if (a[0] == '-' || a[0] == '+') { a++; alen--; } |
|
2686
|
2 |
0 |
while (alen > 0 && *a == '0') { a++; alen--; } |
|
|
0 |
2 |
while (alen > 0 && *a == '0') { a++; alen--; } |
|
2688
|
0 |
2 |
if (aneg != bneg) return min ? (bneg == 1) : (aneg == 1); |
|
|
0 |
0 |
if (aneg != bneg) return min ? (bneg == 1) : (aneg == 1); |
|
2689
|
0 |
2 |
if (aneg == 1) min = !min; |
|
2690
|
0 |
2 |
if (alen != blen) return min ? (alen > blen) : (blen > alen); |
|
|
0 |
0 |
if (alen != blen) return min ? (alen > blen) : (blen > alen); |
|
2692
|
2 |
0 |
for (i = 0; i < blen; i++) |
|
2693
|
2 |
0 |
if (a[i] != b[i]) |
|
2694
|
1 |
1 |
return min ? (a[i] > b[i]) : (b[i] > a[i]); |
|
2704
|
6 |
0 |
if (s[0] == '-' || s[0] == '+') s++; |
|
|
0 |
6 |
if (s[0] == '-' || s[0] == '+') s++; |
|
2705
|
0 |
6 |
while (s[0] == '0') s++; |
|
2710
|
34 |
5 |
for (i = 0, len = strlen(s); i < len; i++) { |
|
2712
|
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; |
|
2713
|
0 |
34 |
if (d >= base) croak("Invalid digit for base %d", base); |
|
2714
|
1 |
33 |
if (n > max) return 0; /* Overflow */ |
|
2725
|
13 |
0 |
if (len < 0 || len > BITS_PER_WORD) |
|
|
0 |
13 |
if (len < 0 || len > BITS_PER_WORD) |
|
2727
|
63 |
13 |
for (i = 0; i < len; i++) { |
|
2729
|
0 |
63 |
if (n > (UV_MAX-d)/base) break; /* overflow */ |
|
2742
|
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; |
|
2744
|
0 |
0 |
if (r[0] >= (UV) base) return 0; /* TODO: We don't apply extended carry */ |
|
2748
|
0 |
0 |
if (base == 2 || base == 16) { |
|
|
0 |
0 |
if (base == 2 || base == 16) { |
|
2750
|
0 |
0 |
*s++ = (base == 2) ? 'b' : 'x'; |
|
2752
|
0 |
0 |
for (i = 0; i < len; i++) { |
|
2754
|
0 |
0 |
s[i] = (d < 10) ? '0'+d : 'a'+d-10; |
|
2765
|
17 |
0 |
if (base < 2 || length > 128) return -1; |
|
|
0 |
17 |
if (base < 2 || length > 128) return -1; |
|
2767
|
10 |
7 |
if (base == 2) { |
|
2768
|
77 |
10 |
for (d = 0; n; n >>= 1) |
|
2771
|
24 |
7 |
for (d = 0; n; n /= base) |
|
2774
|
11 |
6 |
if (length < 0) length = d; |
|
2775
|
26 |
17 |
while (d < length) |
|
2785
|
0 |
3 |
if (len < 0) return -1; |
|
2786
|
0 |
3 |
if (base > 36) croak("invalid base for string: %d", base); |
|
2788
|
18 |
3 |
for (i = 0; i < len; i++) { |
|
2790
|
18 |
0 |
s[i] = (dig < 10) ? '0'+dig : 'a'+dig-10; |
|
2800
|
0 |
1 |
if (hi < 0) { |
|
2812
|
19 |
1 |
} while (sum); |
|
2833
|
10 |
1 |
for (i=0; i < slen/2; i++) { |
|
2839
|
0 |
1 |
if (isneg) { |
|
2840
|
0 |
0 |
for (i = slen; i > 0; i--) |
|
2855
|
473541 |
472642 |
while (n /= p) s += n % 2; |
|
2860
|
0 |
0 |
while (n /= p) s += n % 2; |
|
2864
|
428809 |
472642 |
if (p > a) { |
|
2867
|
472642 |
0 |
UV pow = (n <= 4294967295UL) ? _catalan_v32(a<<1,p) : _catalan_v(a<<1,p); |
|
2869
|
186211 |
286431 |
: (pow == 1) ? mulmod(m,p,n) |
|
2870
|
185962 |
249 |
: mulmod(m,powmod(p,pow,n),n); |
|
2875
|
13 |
5 |
while (n /= p) |
|
2876
|
0 |
13 |
if (n % 2) |
|
2884
|
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; |
|
2885
|
0 |
3 |
if (is_prob_prime(n)) return 1; |
|
2903
|
0 |
3 |
if (nfactors == 2) { /* Conditions from Aebi and Cairns (2008) */ |
|
2904
|
0 |
0 |
if (n < UVCONST(10000000000)) return 0; /* Page 9 */ |
|
2905
|
0 |
0 |
if (2*factors[0]+1 >= factors[1]) return 0; /* Corollary 2 and 3 */ |
|
2909
|
5 |
3 |
for (i = 0; i < nfactors; i++) { |
|
2910
|
0 |
5 |
if (_catalan_vtest(a << 1, factors[i])) |
|
2922
|
16 |
3 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
2923
|
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 ) { |
|
2929
|
1 |
2 |
return (a & 1) ? (m==(n-1)) : (m==1); |
|
2936
|
10 |
35592 |
if (x == 0) return y; |
|
2938
|
19773 |
15819 |
if (y & 1) { /* Optimize y odd */ |
|
2939
|
19773 |
0 |
x >>= ctz(x); |
|
2940
|
370745 |
19773 |
while (x != y) { |
|
2941
|
51792 |
318953 |
if (x < y) { y -= x; y >>= ctz(y); } |
|
|
51792 |
0 |
if (x < y) { y -= x; y >>= ctz(y); } |
|
2942
|
318953 |
0 |
else { x -= y; x >>= ctz(x); } |
|
2947
|
1 |
15818 |
if (y == 0) return x; |
|
2950
|
15818 |
0 |
x2 = ctz(x); |
|
2951
|
15818 |
0 |
y2 = ctz(y); |
|
2956
|
187858 |
15818 |
while (x != y) { |
|
2957
|
14906 |
172952 |
if (x < y) { |
|
2959
|
14906 |
0 |
y >>= ctz(y); |
|
2962
|
172952 |
0 |
x >>= ctz(x); |
|
2976
|
6 |
4 |
return (n < NTAU) ? tau_table[n] : 0; |
|
2983
|
4 |
401 |
if (lim*lim == b2) lim--; |
|
2984
|
43 |
362 |
if (s > lim) return 0; |
|
2986
|
337 |
25 |
if ((lim-s) < 70) { /* Iterate looking for divisors */ |
|
2987
|
6767 |
337 |
for (i = s; i <= lim; i++) |
|
2988
|
106 |
6661 |
if (b2 % i == 0) |
|
2992
|
56 |
0 |
for (i = 0; i < ndivisors && divs[i] <= lim; i++) |
|
|
31 |
25 |
for (i = 0; i < ndivisors && divs[i] <= lim; i++) |
|
2993
|
6 |
25 |
if (divs[i] >= s) |
|
3007
|
1 |
95 |
if (n == 0) return -1; |
|
3008
|
82 |
13 |
if (nmod4 == 1 || nmod4 == 2) return 0; |
|
|
8 |
74 |
if (nmod4 == 1 || nmod4 == 2) return 0; |
|
3009
|
1 |
73 |
if (n == 3) return 4; |
|
3016
|
18 |
55 |
if (b == 1) |
|
3020
|
405 |
73 |
for (; b2 = (n + b*b) >> 2, 3*b2 < n; b += 2) { |
|
3025
|
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); |
|
3030
|
0 |
25300 |
MPUassert(k >= 3, "is_polygonal root < 3"); |
|
3032
|
46 |
25254 |
if (n <= 1) return n; |
|
3033
|
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; |
|
3034
|
108 |
24948 |
if (k == 3) { |
|
3035
|
0 |
108 |
if (n >= UV_MAX/8) *overflow = 1; |
|
3039
|
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; |
|
3043
|
0 |
25056 |
if (D+R <= D) *overflow = 1; |
|
3045
|
25056 |
0 |
if (*overflow || !is_perfect_square(D)) return 0; |
|
|
24138 |
918 |
if (*overflow || !is_perfect_square(D)) return 0; |
|
3048
|
522 |
396 |
if ((D % R) != 0) return 0; |
|
3060
|
3 |
5 |
while (f == 0) /* We can handle n! overflow if we have a valid k */ |
|
3063
|
1 |
4 |
if (k/f >= (UV)n) |
|
3066
|
45 |
5 |
for (i = 0; i < n; i++) |
|
3068
|
37 |
5 |
for (i = si; i < n-1; i++) { |
|
3072
|
19 |
18 |
if (p > 0) { |
|
3073
|
47 |
19 |
for (j = i+p, t = vec[j]; j > i; j--) |
|
3085
|
2 |
4 |
if (f == 0) return 0; |
|
3086
|
38 |
4 |
for (i = 0; i < n-1; i++) { |
|
3087
|
302 |
38 |
for (j = i+1, k = 0; j < n; j++) |
|
3088
|
137 |
165 |
if (vec[j] < vec[i]) |
|
3090
|
0 |
38 |
if ((UV)k > (UV_MAX-num)/f) return 0; /* overflow */ |
|
3111
|
0 |
3 |
if (k > n) k = n; |
|
3113
|
3 |
0 |
if (k == 0) { /* 0 of n */ |
|
3114
|
1 |
2 |
} else if (k == 1) { /* 1 of n. Pick one at random */ |
|
3116
|
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 */ |
|
3119
|
0 |
2 |
} else if (k == 2) { /* 2 of n. Pick 2 skipping dup */ |
|
3122
|
0 |
0 |
if (S[1] >= S[0]) S[1]++; |
|
3123
|
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 */ |
|
3124
|
0 |
0 |
for (i = 0; i < k; i++) { |
|
3127
|
0 |
0 |
for (j = 0; j < i; j++) |
|
3128
|
0 |
0 |
if (S[j] == S[i]) |
|
3130
|
0 |
0 |
} while (j < i); |
|
3132
|
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 */ |
|
3133
|
0 |
0 |
for (j = 0; j < k; ) { |
|
3134
|
0 |
0 |
for (i = j; i < k; i++) /* Fill S[j .. k-1] then sort S */ |
|
3137
|
0 |
0 |
for (j = 0, i = 1; i < k; i++) /* Find and remove dups. O(n). */ |
|
3138
|
0 |
0 |
if (S[j] != S[i]) |
|
3143
|
0 |
0 |
for (i = 0; i < k; i++) { |
|
3147
|
1 |
1 |
} else if (k < n/4) { /* k of n. Pick k with mask */ |
|
3149
|
1 |
0 |
if (n <= 32*8) mask = smask; |
|
3150
|
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); |
|
3151
|
4 |
1 |
for (i = 0; i < k; i++) { |
|
3154
|
0 |
4 |
} while ( mask[j>>5] & (1U << (j&0x1F)) ); |
|
3158
|
0 |
1 |
if (mask != smask) Safefree(mask); |
|
3159
|
0 |
1 |
} else if (k < n) { /* k of n. FYK shuffle n, pick k */ |
|
3161
|
0 |
0 |
New(0, T, n, UV); |
|
3162
|
0 |
0 |
for (i = 0; i < n; i++) |
|
3164
|
0 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
|
0 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
3171
|
100 |
1 |
for (i = 0; i < n; i++) |
|
3173
|
100 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
|
99 |
1 |
for (i = 0; i < k && i <= n-2; i++) { |
|
3182
|
0 |
1 |
if (n < 1) |