| line |
true |
false |
branch |
|
50
|
126 |
0 |
if (len == 0 || v < L[0] || v > L[len-1]) |
|
|
126 |
0 |
if (len == 0 || v < L[0] || v > L[len-1]) |
|
|
57 |
69 |
if (len == 0 || v < L[0] || v > L[len-1]) |
|
54
|
124 |
69 |
while (lo < hi) { |
|
56
|
92 |
32 |
if (L[mid] < v) lo = mid + 1; |
|
59
|
9 |
60 |
return (L[lo] == v) ? lo+1 : 0; |
|
64
|
35 |
0 |
if (len == 0 || v < L[0] || v > L[len-1]) |
|
|
23 |
12 |
if (len == 0 || v < L[0] || v > L[len-1]) |
|
|
6 |
17 |
if (len == 0 || v < L[0] || v > L[len-1]) |
|
68
|
29 |
17 |
while (lo < hi) { |
|
70
|
20 |
9 |
if (L[mid] < v) lo = mid + 1; |
|
73
|
3 |
14 |
return (L[lo] == v) ? lo+1 : 0; |
|
80
|
0 |
0 |
while (ia < alen && ib < blen) { |
|
|
0 |
0 |
while (ia < alen && ib < blen) { |
|
81
|
0 |
0 |
if (A[ia] == B[ib]) return 1; |
|
82
|
0 |
0 |
else if (A[ia] < B[ib]) ia++; |
|
90
|
0 |
0 |
while (ia < alen && ib < blen) { |
|
|
0 |
0 |
while (ia < alen && ib < blen) { |
|
91
|
0 |
0 |
if (A[ia] == B[ib]) return 1; |
|
92
|
0 |
0 |
else if (A[ia] < B[ib]) ia++; |
|
142
|
1593513 |
4024 |
if (n < UVCONST(500000000)) { |
|
144
|
16741 |
1576772 |
if (n < 11) return 0xAC >> n & 1; |
|
145
|
1019277 |
557495 |
if (is_divis_2_3_5_7(n)) return 0; |
|
|
677718 |
341559 |
if (is_divis_2_3_5_7(n)) return 0; |
|
|
601832 |
75886 |
if (is_divis_2_3_5_7(n)) return 0; |
|
|
86465 |
515367 |
if (is_divis_2_3_5_7(n)) return 0; |
|
148
|
23856 |
491511 |
if (n < 30*NPRIME_SIEVE30) { |
|
154
|
53255 |
438256 |
if (n <= get_prime_cache(0,0)) { |
|
157
|
48396 |
4859 |
if (!(n%11) || !(n%13)) return 0; |
|
|
3783 |
44613 |
if (!(n%11) || !(n%13)) return 0; |
|
158
|
44613 |
0 |
if (n <= get_prime_cache(0, &sieve)) { |
|
163
|
44613 |
0 |
if (isprime >= 0) |
|
175
|
80861 |
265 |
if (n < 30*NPRIME_SIEVE30) { |
|
177
|
80860 |
1 |
if (next != 0) return next; |
|
180
|
0 |
266 |
if (n >= MPU_MAX_PRIME) return 0; /* Overflow */ |
|
182
|
84 |
182 |
if (n < get_prime_cache(0,0)) { |
|
185
|
84 |
0 |
next = (n < sieve_size) ? next_prime_in_sieve(sieve, n, sieve_size) : 0; |
|
187
|
84 |
0 |
if (next != 0) return next; |
|
194
|
3155 |
182 |
} while (!is_prob_prime(n)); |
|
203
|
15071 |
2193 |
if (n < 30*NPRIME_SIEVE30) |
|
206
|
31 |
2162 |
if (n < get_prime_cache(0,0)) { |
|
209
|
31 |
0 |
prev = (n < sieve_size) ? prev_prime_in_sieve(sieve, n) : 0; |
|
211
|
31 |
0 |
if (prev != 0) return prev; |
|
218
|
7088 |
2162 |
} while (!is_prob_prime(n)); |
|
229
|
7615 |
1932 |
if (n < 727) |
|
231
|
7494 |
121 |
- (n < 144 ? _cor[n/16] >> n%16*2 & 3 : 0); |
|
235
|
1894 |
38 |
if (n < 59471) /* Special */ |
|
238
|
29 |
9 |
if (n < 1333894) /* Dusart 2018 x > 1 */ |
|
241
|
9 |
0 |
if (n < 883495117) /* Dusart 2022 x > 1 */ |
|
261
|
0 |
0 |
} while ((val = t)); |
|
263
|
0 |
0 |
while (--s > ptr) { char c = *s; *s = *ptr; *ptr++ = c; } |
|
268
|
0 |
0 |
if (res == -1) croak("print_primes write error"); |
|
274
|
0 |
0 |
if ((low <= 2) && (high >= 2)) bend += my_sprint(bend,2); |
|
|
0 |
0 |
if ((low <= 2) && (high >= 2)) bend += my_sprint(bend,2); |
|
275
|
0 |
0 |
if ((low <= 3) && (high >= 3)) bend += my_sprint(bend,3); |
|
|
0 |
0 |
if ((low <= 3) && (high >= 3)) bend += my_sprint(bend,3); |
|
276
|
0 |
0 |
if ((low <= 5) && (high >= 5)) bend += my_sprint(bend,5); |
|
|
0 |
0 |
if ((low <= 5) && (high >= 5)) bend += my_sprint(bend,5); |
|
277
|
0 |
0 |
if (low < 7) low = 7; |
|
279
|
0 |
0 |
if (low <= high) { |
|
283
|
0 |
0 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
284
|
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 ) |
|
286
|
0 |
0 |
if (bend-buf > 8000) { bend = write_buf(fd, buf, bend); } |
|
291
|
0 |
0 |
if (bend > buf) { bend = write_buf(fd, buf, bend); } |
|
311
|
0 |
180 |
if (hi < lo) croak("range_mobius error hi %"UVuf" < lo %"UVuf"\n", hi, lo); |
|
314
|
91 |
89 |
if (sqrtn*sqrtn != hi && sqrtn < (UVCONST(1)<<(BITS_PER_WORD/2))-1) sqrtn++; |
|
|
90 |
1 |
if (sqrtn*sqrtn != hi && sqrtn < (UVCONST(1)<<(BITS_PER_WORD/2))-1) sqrtn++; |
|
317
|
66 |
114 |
if (hi < 100 || count <= 10 || (hi > (1UL<<25) && count < icbrt(hi)/4)) { |
|
|
61 |
5 |
if (hi < 100 || count <= 10 || (hi > (1UL<<25) && count < icbrt(hi)/4)) { |
|
|
0 |
61 |
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)) { |
|
318
|
999 |
119 |
for (i = 0; i < count; i++) |
|
324
|
61 |
0 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
61 |
0 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
183 |
4060 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
122 |
61 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
61 |
61 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
830 |
3230 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
3 |
827 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
0 |
827 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
3 |
827 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
0 |
4057 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
58 |
4182 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
326
|
187 |
3995 |
if (p > nextlog) { |
|
330
|
0 |
4182 |
for (i = P_GT_LO(p, p, lo); i >= lo && i <= hi; i += p) |
|
|
147933046 |
0 |
for (i = P_GT_LO(p, p, lo); i >= lo && i <= hi; i += p) |
|
|
147928864 |
4182 |
for (i = P_GT_LO(p, p, lo); i >= lo && i <= hi; i += p) |
|
332
|
0 |
4182 |
for (i = P_GT_LO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
|
28516137 |
0 |
for (i = P_GT_LO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
|
28511955 |
4182 |
for (i = P_GT_LO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
336
|
10 |
51 |
logp = (unsigned char)log2floor(lo); |
|
338
|
63056243 |
61 |
for (i = 0; i < count; i++) { |
|
340
|
747 |
63055496 |
if (i >= nextlogi) nextlogi = (UVCONST(2) << ++logp) - lo; |
|
341
|
24722510 |
38333733 |
if (a & 0x80) { a = 0; } |
|
342
|
9939206 |
28394527 |
else if (a >= logp) { a = 1 - 2*(a&1); } |
|
346
|
51 |
10 |
if (lo == 0) mu[0] = 0; |
|
359
|
0 |
50 |
New(0, M, hi+1, short); |
|
361
|
63028281 |
50 |
for (i = 1; i <= hi; i++) |
|
424
|
148600 |
29552 |
if (H[idx].n == n) { |
|
436
|
15144 |
178152 |
if (n <= maxmu) |
|
439
|
148600 |
29552 |
if (_get_mert_hash(H, hsize, n, &sum)) |
|
453
|
15144 |
14408 |
if (s != ns && s != ns+1) croak("mertens s / ns"); |
|
|
0 |
15144 |
if (s != ns && s != ns+1) croak("mertens s / ns"); |
|
457
|
144838979 |
29552 |
for (k = 2; k <= ns; k++) { |
|
460
|
144661045 |
177934 |
mnk = (nk <= maxmu) ? M[nk] : _rmertens(nk, maxmu, M, H, hsize); |
|
461
|
144838979 |
0 |
mk = (k <= maxmu) ? M[k] : _rmertens(k, maxmu, M, H, hsize); |
|
464
|
15144 |
14408 |
if (s > ns) |
|
478
|
0 |
50 |
if (maxmu > 100000000UL) { |
|
487
|
0 |
50 |
if (maxmu > UVCONST(7613644883)) maxmu = UVCONST(7613644883); |
|
501
|
18 |
34 |
if (n <= 512) { |
|
505
|
61 |
18 |
for (j = j*16 + 1; j <= n; j++) |
|
511
|
0 |
34 |
Newz(0, H, hsize, mertens_value_t); |
|
527
|
16 |
25 |
if (hi < 16) hi = 15; |
|
530
|
25 |
16 |
if (hi >= 16) memset(l+16, -1, hi-16+1); |
|
532
|
34 |
41 |
for (a = 16; a <= hi; a = b+1) { |
|
535
|
34 |
0 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
|
34 |
0 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
|
102 |
25 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
|
68 |
34 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
|
34 |
34 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
|
0 |
25 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
|
0 |
25 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
|
34 |
93 |
START_DO_FOR_EACH_PRIME(2, isqrt(b)) { |
|
536
|
853 |
93 |
for (k = 2*p; k <= b; k += p) { |
|
537
|
319 |
534 |
if (k >= a) |
|
547
|
0 |
60 |
if (n < 16) |
|
550
|
30 |
30 |
return( (prime_bigomega(n) & 1) ? -1 : 1 ); |
|
559
|
41 |
16 |
if (n <= 96) { |
|
561
|
820 |
41 |
for (sum = 0, j = 1; j <= n; j++) |
|
568
|
0 |
16 |
Newz(0, H, hsize, mertens_value_t); |
|
572
|
109730 |
0 |
for (k = 2; k <= sqrtn; k++) { |
|
574
|
16 |
109714 |
if (nk == 1) break; |
|
575
|
109546 |
168 |
sum += (nk <= maxmu) ? M[nk] : _rmertens(nk, maxmu, M, H, hsize); |
|
594
|
0 |
0 |
if (hi < lo) croak("range_liouvillle error hi %"UVuf" < lo %"UVuf"\n",hi,lo); |
|
597
|
0 |
0 |
for (i = 0; i < hi-lo+1; i++) |
|
598
|
0 |
0 |
l[i] = (nf[i] & 1) ? -1 : 1; |
|
608
|
8 |
259 |
if (n < 8) return _totient[n]; |
|
609
|
9 |
250 |
if ((n & (n-1)) == 0) return n >> 2; |
|
611
|
250 |
0 |
i = ctz(n); |
|
612
|
94 |
156 |
if (i > 0) { |
|
614
|
20 |
74 |
lambda <<= (i>2) ? i-2 : i-1; |
|
620
|
340 |
250 |
for (i = 0; i < nfactors; i++) { |
|
622
|
137 |
250 |
while (i+1 < nfactors && p == fac[i+1]) { |
|
|
47 |
90 |
while (i+1 < nfactors && p == fac[i+1]) { |
|
663
|
44318 |
0 |
if (n > 0) { |
|
676
|
181339 |
78625 |
while (bit >>= 1) { |
|
678
|
94064 |
87275 |
if (e & bit) |
|
701
|
10994 |
67631 |
if (k == 4) return (int)(sqrtf(sqrtf(y)) + 0.5f); |
|
727
|
159351 |
67631 |
while (msbit >>= 1) { |
|
729
|
94064 |
65287 |
if (k & msbit) |
|
742
|
15878 |
35868 |
uint32_t const msb = 4 << (k >= 8); |
|
757
|
8147 |
132032 |
if (n <= 1) return (k != 0 && n != 0); |
|
|
8147 |
0 |
if (n <= 1) return (k != 0 && n != 0); |
|
|
8138 |
9 |
if (n <= 1) return (k != 0 && n != 0); |
|
773
|
31687 |
40932 |
if (n >> k == 0) return 1; |
|
775
|
32384 |
8548 |
if (k <= MAX_IROOTN) return _irootn(n,k); |
|
777
|
373 |
8175 |
if (k > MPU_MAX_POW3) return 1 + (k < BITS_PER_WORD); |
|
|
370 |
3 |
if (k > MPU_MAX_POW3) return 1 + (k < BITS_PER_WORD); |
|
778
|
383 |
7792 |
if (k >= BITS_PER_WORD/2) return 2 + (n >= ipow(3,k)); |
|
|
100 |
283 |
if (k >= BITS_PER_WORD/2) return 2 + (n >= ipow(3,k)); |
|
782
|
7792 |
0 |
uint32_t lo = 1U << (log2floor(n)/k); |
|
784
|
7494 |
298 |
if (hi >= lo*2) hi = lo*2 - 1; |
|
786
|
8155 |
7792 |
while (lo < hi) { |
|
788
|
6571 |
1584 |
if (ipow(mid,k) > n) hi = mid-1; |
|
799
|
10 |
114071 |
if (n == 0) return !k; /* 0^0 => 1, 0^x => 0 */ |
|
800
|
7925 |
106146 |
if (n == 1) return 1; /* 1^0 => 1, 1^x => 1 */ |
|
802
|
102752 |
3394 |
if (k <= MPU_MAX_POW3) { |
|
803
|
17 |
102735 |
if (k == 0) return 1; |
|
804
|
51 |
102684 |
if (k == 1) return n; |
|
805
|
100160 |
2524 |
return (n <= root_max[k]) ? ipow(n,k) : UV_MAX; |
|
808
|
15916 |
287 |
while (k) { |
|
809
|
8543 |
7373 |
if (k & 1) { if (UV_MAX/n < p) return UV_MAX; p *= n; } |
|
|
753 |
7790 |
if (k & 1) { if (UV_MAX/n < p) return UV_MAX; p *= n; } |
|
811
|
14876 |
287 |
if (k) { if (UV_MAX/n < n) return UV_MAX; n *= n; } |
|
|
2354 |
12522 |
if (k) { if (UV_MAX/n < n) return UV_MAX; n *= n; } |
|
835
|
62585 |
9 |
if (n < 2 || k == 1) { |
|
|
18 |
62567 |
if (n < 2 || k == 1) { |
|
836
|
22 |
5 |
if (root) *root = n; |
|
839
|
0 |
62567 |
if (k == 0) |
|
841
|
1 |
62566 |
if (k > MPU_MAX_POW3) { |
|
842
|
1 |
0 |
if (root) *root = 2; |
|
843
|
1 |
0 |
return (k < BITS_PER_WORD && n == (UV)1 << k); |
|
|
0 |
1 |
return (k < BITS_PER_WORD && n == (UV)1 << k); |
|
846
|
65 |
62501 |
if (k == 2) return is_perfect_square_ret(n,root); |
|
849
|
20163 |
42338 |
if ((1U << (n&31)) & _rootmask32[k]) return 0; |
|
851
|
15459 |
26879 |
if (k == 3) { |
|
852
|
13418 |
2041 |
r = n % 117; if ((r*833230740) & (r*120676722) & 813764715) return 0; |
|
854
|
2040 |
1 |
if (root) *root = r; |
|
858
|
8211 |
26879 |
for (msbit = 8 /* k >= 4 */; k >= msbit; msbit <<= 1) ; |
|
861
|
26879 |
0 |
if (root) *root = r; |
|
881
|
1 |
17978 |
if (n <= 1) { |
|
882
|
0 |
1 |
if (root) *root = n; |
|
886
|
17947 |
31 |
if ((n <= 3) || (n == UV_MAX)) return 0; |
|
|
0 |
17947 |
if ((n <= 3) || (n == UV_MAX)) return 0; |
|
887
|
27 |
17920 |
if ((n & (n-1)) == 0) PORET(2,ctz(n)); |
|
|
27 |
0 |
if ((n & (n-1)) == 0) PORET(2,ctz(n)); |
|
889
|
407 |
17920 |
while (is_perfect_square_ret(n,&r)) { n = r; k *= 2; } |
|
890
|
118 |
17920 |
while (is_power_ret(n, 3, &r)) { n = r; k *= 3; } |
|
891
|
18 |
17920 |
while (is_power_ret(n, 5, &r)) { n = r; k *= 5; } |
|
893
|
7 |
17913 |
if (is_power_ret(n, 7, &r)) PORET(r,7); |
|
899
|
14448 |
3459 |
if (_maxpow128[n % 128] < 13) goto poreturn; |
|
901
|
4 |
3455 |
if (is_power_ret(n, 13, &r)) PORET(r,13); |
|
902
|
7 |
3448 |
if (is_power_ret(n, 17, &r)) PORET(r,17); |
|
904
|
3407 |
41 |
if (n >= 1162261467) { |
|
922
|
35 |
6 |
if (t != 0) { n = r; k *= t; } |
|
926
|
17435 |
512 |
if (k <= 1) return 0; |
|
927
|
301 |
211 |
if (root) *root = n; |
|
937
|
342 |
0 |
if (x==0 || y==0) return 0; |
|
|
0 |
342 |
if (x==0 || y==0) return 0; |
|
939
|
1 |
341 |
if (UV_MAX/x < y) return 0; |
|
948
|
1310 |
0 |
if (k < 2 || n < 2) return 0; |
|
|
5 |
1305 |
if (k < 2 || n < 2) return 0; |
|
949
|
578 |
727 |
if (k == 2) return ctz(n); |
|
|
578 |
0 |
if (k == 2) return ctz(n); |
|
950
|
59 |
727 |
while ( !(n % kpower) ) { |
|
959
|
0 |
26 |
if (k <= 1) { v = 0; } |
|
960
|
26 |
0 |
else if (k == 2) { v = ctz(n); n >>= v; } |
|
|
26 |
0 |
else if (k == 2) { v = ctz(n); n >>= v; } |
|
962
|
0 |
0 |
for (v=0; !(n % k); v++) |
|
973
|
388 |
840 |
if (b <= 2) |
|
974
|
388 |
0 |
return b == 2 ? log2floor(n) : 0; /* b < 2 is invalid */ |
|
|
388 |
0 |
return b == 2 ? log2floor(n) : 0; /* b < 2 is invalid */ |
|
975
|
16 |
824 |
if (b > n) |
|
977
|
0 |
824 |
if (n > UV_MAX/b) { |
|
981
|
2017 |
824 |
for (v = b; v <= n; v *= b) |
|
989
|
0 |
407 |
if (hi < lo) return 0; |
|
992
|
405 |
2 |
if (lo == 0) isf[0] = 0; |
|
996
|
633 |
34 |
while (p < 7 && p <= sqrthi) { |
|
|
260 |
373 |
while (p < 7 && p <= sqrthi) { |
|
997
|
3 |
257 |
for (p2=p*p, i = P_GT_LO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
|
81151 |
0 |
for (p2=p*p, i = P_GT_LO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
|
80891 |
260 |
for (p2=p*p, i = P_GT_LO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
999
|
125 |
135 |
p += 1 + (p > 2); |
|
1002
|
27 |
380 |
if (sqrthi >= 7) { /* Sieve multiples of higher prime squares */ |
|
1006
|
27 |
27 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
1007
|
664 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
27 |
637 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
637 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
664 |
12 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
39 |
27 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
1008
|
385 |
252 |
for (p2=p*p, i = P_GT_LO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
|
10555 |
0 |
for (p2=p*p, i = P_GT_LO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
|
9918 |
637 |
for (p2=p*p, i = P_GT_LO(p2, p2, lo); i >= lo && i <= hi; i += p2) |
|
1030
|
12049 |
8934 |
if (n <= 1 || k == 0) return n; |
|
|
11 |
12038 |
if (n <= 1 || k == 0) return n; |
|
1031
|
12037 |
1 |
if (k >= BITS_PER_WORD || n > _max_ps_n[k]) return 0; |
|
|
11 |
12026 |
if (k >= BITS_PER_WORD || n > _max_ps_n[k]) return 0; |
|
1032
|
3091 |
8935 |
if (n == 2) return 1 + (UVCONST(1) << k); |
|
1036
|
3 |
8932 |
if (k == 1) return a; |
|
1037
|
4131 |
4801 |
if (k == 3) return a2; |
|
1039
|
4531 |
270 |
if (k <= 8 && n <= _max_ps_calc[k]) { /* Use simple formula if possible */ |
|
|
4521 |
10 |
if (k <= 8 && n <= _max_ps_calc[k]) { /* Use simple formula if possible */ |
|
1040
|
2223 |
2298 |
if (k == 2) return a * (2*n+1) / 3; |
|
1041
|
1212 |
1086 |
if (k == 4) return a * (2*n+1) * (3*n*(n+1)-1) / 15; |
|
1042
|
535 |
551 |
if (k == 5) return a2 * (4*a - 1) / 3; |
|
1043
|
269 |
282 |
if (k == 6) return a * (2*n+1) * (n*((n*(n*(3*n+6)))-3)+1) / 21; |
|
1044
|
161 |
121 |
if (k == 7) return a2 * (6*a2 - 4*a + 1) / 3; |
|
1045
|
121 |
0 |
if (k == 8) return a * (2*n+1) * (n*(n*(n*(n*(n*(5*n+15)+5)-15)-1)+9)-3)/45; |
|
1048
|
10 |
270 |
if (k <= 8 && k < n) { |
|
|
10 |
0 |
if (k <= 8 && k < n) { |
|
1050
|
46 |
10 |
for (sum = 0, r = 1; r <= k; r++) { |
|
1059
|
991 |
270 |
for (i = 3; i <= n; i++) |
|
1069
|
3 |
0 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
3 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
3 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
3 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
1075
|
20 |
3 |
for (i = 0; i < slen; i++) { /* Chunks of 8 digits */ |
|
1076
|
154 |
18 |
for (j = 0, d = 0, power = 1; j < 8 && len > 0; j++, power *= 10) { |
|
|
152 |
2 |
for (j = 0, d = 0, power = 1; j < 8 && len > 0; j++, power *= 10) { |
|
1078
|
0 |
152 |
if (v > 9) croak("Parameter '%s' must be a single decimal number",ptr); |
|
1084
|
425 |
3 |
while (slen > 1) { |
|
1085
|
208 |
217 |
if (s[slen-1] & 1) count++; |
|
1087
|
17 |
408 |
if (s[0] == 1) { |
|
1088
|
0 |
17 |
if (--slen == 0) break; |
|
1091
|
2051 |
425 |
for (i = 0; i < slen; i++) { |
|
1092
|
1626 |
425 |
if ( (i+1) < slen && sptr[i] & 1 ) sptr[i+1] += 100000000; |
|
|
806 |
820 |
if ( (i+1) < slen && sptr[i] & 1 ) sptr[i+1] += 100000000; |
|
1097
|
80 |
3 |
for (d = s[0]; d > 0; d >>= 1) |
|
1098
|
38 |
42 |
if (d & 1) |
|
1110
|
8213 |
2913 |
while (a) { |
|
1111
|
8213 |
0 |
int r = padic2(a); |
|
1112
|
3164 |
5049 |
if (r) { |
|
1113
|
2388 |
776 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
|
1223 |
1165 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
|
402 |
821 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
1116
|
1670 |
6543 |
if (a & b & 2) s = -s; |
|
1119
|
2909 |
4 |
return (b == 1) ? s : 0; |
|
1124
|
2894 |
30 |
if (b & 1) return kronecker_uu_sign(a, b, 1); |
|
1125
|
24 |
6 |
if (!(a&1)) return 0; |
|
1127
|
5 |
1 |
r = padic2(b); |
|
1128
|
6 |
0 |
if (r) { |
|
1129
|
4 |
2 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
0 |
4 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
0 |
0 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
1138
|
28 |
15 |
if (a >= 0) return kronecker_uu(a, b); |
|
1139
|
2 |
13 |
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; |
|
1141
|
13 |
0 |
r = padic2(b); |
|
1142
|
2 |
11 |
if (r) { |
|
1143
|
0 |
2 |
if (!(a&1)) return 0; |
|
1144
|
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; |
|
1148
|
9 |
4 |
a = (rem == 0) ? 0 : b-rem; |
|
1153
|
0 |
0 |
if (a >= 0 && b >= 0) |
|
|
0 |
0 |
if (a >= 0 && b >= 0) |
|
1154
|
0 |
0 |
return (b & 1) ? kronecker_uu_sign(a, b, 1) : kronecker_uu(a,b); |
|
1155
|
0 |
0 |
if (b >= 0) |
|
1157
|
0 |
0 |
return kronecker_su(a, -b) * ((a < 0) ? -1 : 1); |
|
1176
|
1120 |
24 |
return (n > MAX_PNPRIM) ? 0 : _pn_prim[n]; |
|
1179
|
26 |
36 |
return (n > MAX_PRIM) ? 0 : _pn_prim[_prim_map[n]]; |
|
1183
|
400 |
77955 |
if (n > (sizeof(UV) <= 4 ? 12 : 20)) return 0; |
|
1184
|
94408 |
77955 |
for (i = 2; i <= n; i++) |
|
1189
|
21 |
157 |
if (n <= 3) return (n ? n-1 : 1); |
|
|
20 |
1 |
if (n <= 3) return (n ? n-1 : 1); |
|
1190
|
4 |
153 |
if (n >= (BITS_PER_WORD == 64 ? 21 : 14)) return 0; |
|
1191
|
72 |
81 |
return (n * subfactorial(n-1) + ((n & 1) ? -1 : 1)); |
|
1196
|
187 |
9927 |
if (k == 0) return 1; |
|
1197
|
1291 |
8636 |
if (k == 1) return n; |
|
1198
|
1078 |
7558 |
if (k >= n) return (k == n); |
|
1199
|
3785 |
3773 |
if (k > n/2) k = n-k; |
|
1200
|
45182 |
7372 |
for (d = 1; d <= k; d++) { |
|
1201
|
596 |
44586 |
if (r >= UV_MAX/n) { /* Possible overflow */ |
|
1205
|
186 |
410 |
if (r >= UV_MAX/nr) return 0; /* Unavoidable overflow */ |
|
1220
|
0 |
190 |
if (m == n) return 1; |
|
1221
|
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; |
|
1222
|
19 |
171 |
if (m == 1) return factorial(n); |
|
1225
|
0 |
171 |
if (f1 == 0) return 0; |
|
1227
|
171 |
0 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
|
0 |
171 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
1230
|
171 |
0 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
|
5 |
166 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
1238
|
24 |
1261 |
if (m == n) return 1; |
|
1239
|
1261 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
1261 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
0 |
1261 |
if (n == 0 || m == 0 || m > n) return 0; |
|
1240
|
210 |
1051 |
if (m == 1) return 1; |
|
1242
|
46 |
1005 |
if ((f = factorial(m)) == 0) return 0; |
|
1243
|
4767 |
932 |
for (j = 1; j <= (IV)m; j++) { |
|
1245
|
66244 |
4694 |
for (k = 1; k <= (IV)n; k++) { |
|
1246
|
66244 |
0 |
if (t == 0 || j >= IV_MAX/t) return 0; |
|
|
73 |
66171 |
if (t == 0 || j >= IV_MAX/t) return 0; |
|
1249
|
2137 |
2557 |
if ((m-j) & 1) t *= -1; |
|
1258
|
0 |
192 |
if (m == n) return 1; |
|
1259
|
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; |
|
1260
|
19 |
173 |
if (m == 1) { |
|
1262
|
0 |
19 |
if (f>(UV)IV_MAX) return 0; |
|
1263
|
10 |
9 |
return (n&1) ? ((IV)f) : -((IV)f); |
|
1266
|
816 |
126 |
for (k = 1; k <= (IV)(n-m); k++) { |
|
1270
|
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; |
|
1272
|
35 |
769 |
if (s2 > IV_MAX/t) return 0; |
|
1274
|
430 |
339 |
s += (k & 1) ? -t : t; |
|
1281
|
1 |
23 |
if (n == 0) return 1; |
|
1282
|
8 |
15 |
if (n >= ((BITS_PER_WORD == 64) ? 16 : 10)) return 0; |
|
1283
|
105 |
15 |
for (sum = 1, k = 2; k <= n; k++) |
|
1291
|
21 |
430 |
if (m == 0) return 1; |
|
1292
|
110 |
320 |
if (m > n) return 0; |
|
1293
|
1301 |
316 |
for (i = 1; i < m; i++) { |
|
1294
|
4 |
1297 |
if (UV_MAX/(n-i) < r) return UV_MAX; /* Overflow */ |
|
1301
|
21 |
215 |
if (m == 0) return 1; |
|
1302
|
0 |
215 |
if ((m-1) > (UV_MAX-n)) return UV_MAX; /* Overflow */ |
|
1308
|
0 |
110 |
UV r = (n>=0) ? falling_factorial(n,m) : rising_factorial(-n,m); |
|
1309
|
0 |
110 |
if (r >= IV_MAX) return IV_MAX; /* Overflow */ |
|
1310
|
110 |
0 |
return (n < 0 && (m&1)) ? -(IV)r : (IV)r; |
|
|
50 |
60 |
return (n < 0 && (m&1)) ? -(IV)r : (IV)r; |
|
1314
|
0 |
110 |
UV r = (n>=0) ? rising_factorial(n,m) : falling_factorial(-n,m); |
|
1315
|
0 |
110 |
if (r >= IV_MAX) return IV_MAX; /* Overflow */ |
|
1316
|
110 |
0 |
return (n < 0 && (m&1)) ? -(IV)r : (IV)r; |
|
|
50 |
60 |
return (n < 0 && (m&1)) ? -(IV)r : (IV)r; |
|
1323
|
2 |
58 |
if (n == 1) { *num = 1; *den = 2; return TRUE; } |
|
1325
|
12 |
46 |
if (n & 1) return TRUE; |
|
1348
|
118 |
655 |
if (b-a == 1) { |
|
1351
|
294 |
361 |
} else if (b-a == 2) { |
|
1366
|
2 |
52 |
if (n >= BITS_PER_WORD/2) |
|
1369
|
1 |
51 |
if (n == 0) { |
|
1386
|
7 |
32822 |
if (n < 4) return (n != 0); |
|
1389
|
16438 |
16384 |
if ( !(n & 1) /* 2 only even */ |
|
1390
|
14606 |
1832 |
|| !(n% 9) || !(n%25) || !(n%49) /* not sq free */ |
|
|
14020 |
586 |
|| !(n% 9) || !(n%25) || !(n%49) /* not sq free */ |
|
|
13733 |
287 |
|| !(n% 9) || !(n%25) || !(n%49) /* not sq free */ |
|
1391
|
13303 |
430 |
|| !(n%21) || !(n%39) || !(n%55) || !(n%57) || !(n%93) /* q = 1 mod p */ |
|
|
13071 |
232 |
|| !(n%21) || !(n%39) || !(n%55) || !(n%57) || !(n%93) /* q = 1 mod p */ |
|
|
12870 |
201 |
|| !(n%21) || !(n%39) || !(n%55) || !(n%57) || !(n%93) /* q = 1 mod p */ |
|
|
12724 |
146 |
|| !(n%21) || !(n%39) || !(n%55) || !(n%57) || !(n%93) /* q = 1 mod p */ |
|
|
12639 |
85 |
|| !(n%21) || !(n%39) || !(n%55) || !(n%57) || !(n%93) /* q = 1 mod p */ |
|
1392
|
12549 |
90 |
|| !(n%121) || !(n%169) /* not sq free */ |
|
|
12489 |
60 |
|| !(n%121) || !(n%169) /* not sq free */ |
|
1393
|
12419 |
70 |
|| !(n%111) || !(n%129) || !(n%155) || !(n%183)) /* q = 1 mod p */ |
|
|
12362 |
57 |
|| !(n%111) || !(n%129) || !(n%155) || !(n%183)) /* q = 1 mod p */ |
|
|
12312 |
50 |
|| !(n%111) || !(n%129) || !(n%155) || !(n%183)) /* q = 1 mod p */ |
|
|
37 |
12275 |
|| !(n%111) || !(n%129) || !(n%155) || !(n%183)) /* q = 1 mod p */ |
|
1396
|
97 |
12178 |
if (n <= 200) return 1; /* Filters above were sufficient for tiny inputs */ |
|
1401
|
3466 |
8712 |
if (nfacs == 1) |
|
1403
|
11303 |
8520 |
for (i = 1; i < nfacs; i++) |
|
1404
|
192 |
11111 |
if (facs[i] == facs[i-1]) |
|
1406
|
19511 |
8520 |
for (phi = 1, i = 0; i < nfacs; i++) |
|
1416
|
19446 |
560 |
if (n < 561 || !(n&1)) return 0; |
|
|
9720 |
9726 |
if (n < 561 || !(n&1)) return 0; |
|
1419
|
8646 |
1080 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
8300 |
346 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
8131 |
169 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
8064 |
67 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
47 |
8017 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
1423
|
1334 |
6683 |
if (!(n% 5) && ((n-1) % 4 != 0)) return 0; |
|
|
666 |
668 |
if (!(n% 5) && ((n-1) % 4 != 0)) return 0; |
|
1424
|
918 |
6433 |
if (!(n% 7) && ((n-1) % 6 != 0)) return 0; |
|
|
574 |
344 |
if (!(n% 7) && ((n-1) % 6 != 0)) return 0; |
|
1425
|
567 |
6210 |
if (!(n%11) && ((n-1) % 10 != 0)) return 0; |
|
|
438 |
129 |
if (!(n%11) && ((n-1) % 10 != 0)) return 0; |
|
1426
|
451 |
5888 |
if (!(n%13) && ((n-1) % 12 != 0)) return 0; |
|
|
349 |
102 |
if (!(n%13) && ((n-1) % 12 != 0)) return 0; |
|
1427
|
355 |
5635 |
if (!(n%17) && ((n-1) % 16 != 0)) return 0; |
|
|
306 |
49 |
if (!(n%17) && ((n-1) % 16 != 0)) return 0; |
|
1428
|
302 |
5382 |
if (!(n%19) && ((n-1) % 18 != 0)) return 0; |
|
|
261 |
41 |
if (!(n%19) && ((n-1) % 18 != 0)) return 0; |
|
1429
|
244 |
5179 |
if (!(n%23) && ((n-1) % 22 != 0)) return 0; |
|
|
220 |
24 |
if (!(n%23) && ((n-1) % 22 != 0)) return 0; |
|
1432
|
6 |
5197 |
if (n > 5000000) { |
|
1433
|
1 |
5 |
if (!(n%29) && ((n-1) % 28 != 0)) return 0; |
|
|
1 |
0 |
if (!(n%29) && ((n-1) % 28 != 0)) return 0; |
|
1434
|
1 |
4 |
if (!(n%31) && ((n-1) % 30 != 0)) return 0; |
|
|
1 |
0 |
if (!(n%31) && ((n-1) % 30 != 0)) return 0; |
|
1435
|
1 |
3 |
if (!(n%37) && ((n-1) % 36 != 0)) return 0; |
|
|
1 |
0 |
if (!(n%37) && ((n-1) % 36 != 0)) return 0; |
|
1436
|
1 |
2 |
if (!(n%41) && ((n-1) % 40 != 0)) return 0; |
|
|
1 |
0 |
if (!(n%41) && ((n-1) % 40 != 0)) return 0; |
|
1437
|
1 |
1 |
if (!(n%43) && ((n-1) % 42 != 0)) return 0; |
|
|
1 |
0 |
if (!(n%43) && ((n-1) % 42 != 0)) return 0; |
|
1438
|
1 |
0 |
if (!is_pseudoprime(n,2)) return 0; |
|
1442
|
4664 |
533 |
if (nf.nfactors < 3) |
|
1444
|
1321 |
9 |
for (i = 0; i < nf.nfactors; i++) { |
|
1445
|
1321 |
0 |
if (nf.e[i] > 1 || ((n-1) % (nf.f[i]-1)) != 0) |
|
|
524 |
797 |
if (nf.e[i] > 1 || ((n-1) % (nf.f[i]-1)) != 0) |
|
1454
|
13015 |
144 |
for (i = 0; i < nf.nfactors; i++) { |
|
1456
|
13015 |
0 |
if (d == 0 || (p % d) != 0) |
|
|
8086 |
4929 |
if (d == 0 || (p % d) != 0) |
|
1469
|
68 |
5334 |
if (n < 35) return 0; |
|
1472
|
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)) |
|
1477
|
741 |
2552 |
if (nf.nfactors < 2) |
|
1480
|
34 |
2518 |
if (!factored_is_square_free(nf)) |
|
1488
|
1448 |
1070 |
if (nf.nfactors == 2) { |
|
1490
|
5953 |
0 |
for (i = 0; i < ndivisors; i++) { |
|
1493
|
1448 |
4505 |
if (d >= spf) break; |
|
1494
|
92 |
4413 |
if (is_quasi_base(nf, k)) |
|
1499
|
8453 |
1070 |
for (i = 0; i < ndivisors; i++) { |
|
1502
|
3693 |
4760 |
if (lpf > d && k >= spf) continue; |
|
|
3658 |
35 |
if (lpf > d && k >= spf) continue; |
|
1503
|
3725 |
1070 |
if (k != 0 && is_quasi_base(nf, k)) |
|
|
52 |
3673 |
if (k != 0 && is_quasi_base(nf, k)) |
|
1515
|
121 |
62228 |
if (n < 6) return (n == 4); |
|
1516
|
30389 |
31839 |
if (!(n&1)) return is_prob_prime(n>>1); |
|
1517
|
10345 |
21494 |
if (!(n%3)) return is_prob_prime(n/3); |
|
1518
|
4118 |
17376 |
if (!(n%5)) return is_prob_prime(n/5); |
|
1521
|
64326 |
16 |
for (sp = 4; sp < 60; sp++) { |
|
1523
|
12489 |
51837 |
if (p > n3) |
|
1525
|
4871 |
46966 |
if ((n % p) == 0) |
|
1529
|
12501 |
4 |
if (is_def_prime(n)) return 0; |
|
|
8121 |
4384 |
if (is_def_prime(n)) return 0; |
|
1530
|
4376 |
8 |
if (p > n3) return 1; /* past this, n is a composite and larger than p^3 */ |
|
1533
|
0 |
8 |
if (is_perfect_square_ret(n,&n2)) /* Fast square check */ |
|
1537
|
0 |
8 |
if (factor_one(n, factors, 0, 0) != 2) return 0; |
|
1538
|
8 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
8 |
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])); |
|
|
5 |
3 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
4 |
1 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
3 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
1543
|
42 |
17079 |
if (k == 0) return (n == 1); |
|
1544
|
1052 |
16027 |
if (k == 1) return is_prob_prime(n); |
|
1545
|
1052 |
14975 |
if (k == 2) return is_semiprime(n); |
|
1547
|
2278 |
12697 |
if ((n >> k) == 0) return 0; /* The smallest k-almost prime is 2^k */ |
|
1549
|
26465 |
284 |
while (k > 0 && !(n& 1)) { k--; n >>= 1; } |
|
|
14052 |
12413 |
while (k > 0 && !(n& 1)) { k--; n >>= 1; } |
|
1550
|
18390 |
565 |
while (k > 0 && !(n% 3)) { k--; n /= 3; } |
|
|
6258 |
12132 |
while (k > 0 && !(n% 3)) { k--; n /= 3; } |
|
1551
|
15006 |
727 |
while (k > 0 && !(n% 5)) { k--; n /= 5; } |
|
|
3036 |
11970 |
while (k > 0 && !(n% 5)) { k--; n /= 5; } |
|
1552
|
13858 |
853 |
while (k > 0 && !(n% 7)) { k--; n /= 7; } |
|
|
2014 |
11844 |
while (k > 0 && !(n% 7)) { k--; n /= 7; } |
|
1554
|
8601 |
4096 |
if (k >= 5) { |
|
1555
|
8603 |
0 |
for (sp = 5; k > 1 && n > 1 && sp < NPRIMES_TINY-1; sp++) { |
|
|
8597 |
6 |
for (sp = 5; k > 1 && n > 1 && sp < NPRIMES_TINY-1; sp++) { |
|
|
8597 |
0 |
for (sp = 5; k > 1 && n > 1 && sp < NPRIMES_TINY-1; sp++) { |
|
1557
|
8595 |
2 |
if (n < ipowsafe(p,k)) |
|
1559
|
0 |
2 |
while ((n % p) == 0 && k > 0) |
|
|
0 |
0 |
while ((n % p) == 0 && k > 0) |
|
1564
|
853 |
3249 |
if (k == 0) return (n == 1); |
|
1565
|
541 |
2708 |
if (k == 1) return is_prob_prime(n); |
|
1566
|
777 |
1931 |
if (k == 2) return is_semiprime(n); |
|
1567
|
1817 |
114 |
if (n < ipowsafe(p,k)) return 0; |
|
1574
|
94 |
8 |
if (r) { |
|
1575
|
47 |
47 |
if (neg) r = 16-r; |
|
1576
|
18 |
76 |
if ((r & 3) == 0 && r != 4) return is_square_free(n >> 2); |
|
|
12 |
6 |
if ((r & 3) == 0 && r != 4) return is_square_free(n >> 2); |
|
1577
|
25 |
57 |
if ((r & 3) == 1) return is_square_free(n); |
|
1587
|
970 |
23 |
if (n < 23 || masktab30[n % 30] == 0 || n % 7 == 0) return 0; |
|
|
260 |
710 |
if (n < 23 || masktab30[n % 30] == 0 || n % 7 == 0) return 0; |
|
|
37 |
223 |
if (n < 23 || masktab30[n % 30] == 0 || n % 7 == 0) return 0; |
|
1589
|
223 |
0 |
if (n < HALF_WORD) { |
|
1590
|
51761 |
77 |
for (v = 8; v < n-1 && fac != 0; v++) { |
|
|
51700 |
61 |
for (v = 8; v < n-1 && fac != 0; v++) { |
|
1592
|
114 |
51586 |
if (fac == n-1 && (n % v) != 1) |
|
|
85 |
29 |
if (fac == n-1 && (n % v) != 1) |
|
1596
|
0 |
0 |
for (v = 8; v < n-1 && fac != 0; v++) { |
|
|
0 |
0 |
for (v = 8; v < n-1 && fac != 0; v++) { |
|
1598
|
0 |
0 |
if (fac == n-1 && (n % v) != 1) |
|
|
0 |
0 |
if (fac == n-1 && (n % v) != 1) |
|
1612
|
6670 |
25110 |
if (n < 256) return (int)((_smoebius[n >> 4] >> (2*(n % 16))) & 3) - 1; |
|
1614
|
18829 |
6281 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
|
16735 |
2094 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
|
16068 |
667 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
|
15745 |
323 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
|
15619 |
126 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
|
97 |
15522 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
1617
|
15382 |
140 |
MOB_TESTP(17); MOB_TESTP(19); MOB_TESTP(23); |
|
|
62 |
15320 |
MOB_TESTP(17); MOB_TESTP(19); MOB_TESTP(23); |
|
|
15026 |
434 |
MOB_TESTP(17); MOB_TESTP(19); MOB_TESTP(23); |
|
|
49 |
14977 |
MOB_TESTP(17); MOB_TESTP(19); MOB_TESTP(23); |
|
|
14258 |
1153 |
MOB_TESTP(17); MOB_TESTP(19); MOB_TESTP(23); |
|
|
34 |
14224 |
MOB_TESTP(17); MOB_TESTP(19); MOB_TESTP(23); |
|
1618
|
13084 |
2293 |
MOB_TESTP(29); MOB_TESTP(31); MOB_TESTP(37); |
|
|
21 |
13063 |
MOB_TESTP(29); MOB_TESTP(31); MOB_TESTP(37); |
|
|
12637 |
2719 |
MOB_TESTP(29); MOB_TESTP(31); MOB_TESTP(37); |
|
|
20 |
12617 |
MOB_TESTP(29); MOB_TESTP(31); MOB_TESTP(37); |
|
|
11549 |
3787 |
MOB_TESTP(29); MOB_TESTP(31); MOB_TESTP(37); |
|
|
13 |
11536 |
MOB_TESTP(29); MOB_TESTP(31); MOB_TESTP(37); |
|
1628
|
35552 |
9883 |
if (n < 256) return (_isf[n >> 5] & (1U << (n % 32))) != 0; |
|
1630
|
7738 |
2145 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
|
6953 |
785 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
|
6690 |
263 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
|
6558 |
132 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
|
6500 |
58 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
|
41 |
6459 |
if (!(n % 4) || !(n % 9) || !(n % 25) || !(n % 49) || !(n %121) || !(n %169)) |
|
1633
|
217 |
6242 |
ISF_TESTP(17); ISF_TESTP(19); ISF_TESTP(23); |
|
|
32 |
6210 |
ISF_TESTP(17); ISF_TESTP(19); ISF_TESTP(23); |
|
|
357 |
5853 |
ISF_TESTP(17); ISF_TESTP(19); ISF_TESTP(23); |
|
|
24 |
5829 |
ISF_TESTP(17); ISF_TESTP(19); ISF_TESTP(23); |
|
|
724 |
5105 |
ISF_TESTP(17); ISF_TESTP(19); ISF_TESTP(23); |
|
|
16 |
5089 |
ISF_TESTP(17); ISF_TESTP(19); ISF_TESTP(23); |
|
1634
|
832 |
4257 |
ISF_TESTP(29); ISF_TESTP(31); ISF_TESTP(37); |
|
|
9 |
4248 |
ISF_TESTP(29); ISF_TESTP(31); ISF_TESTP(37); |
|
|
241 |
4007 |
ISF_TESTP(29); ISF_TESTP(31); ISF_TESTP(37); |
|
|
8 |
3999 |
ISF_TESTP(29); ISF_TESTP(31); ISF_TESTP(37); |
|
|
659 |
3340 |
ISF_TESTP(29); ISF_TESTP(31); ISF_TESTP(37); |
|
|
5 |
3335 |
ISF_TESTP(29); ISF_TESTP(31); ISF_TESTP(37); |
|
1641
|
516 |
1 |
if (n == 0 || (n & 1)) return 0; |
|
|
256 |
260 |
if (n == 0 || (n & 1)) return 0; |
|
1645
|
217 |
43 |
if (m & (m+1)) return 0; |
|
1646
|
31 |
12 |
if ((m >> v) != 1) return 0; |
|
1652
|
6 |
14 |
if (!prime_power(n,&p)) return 1; /* Not a prime power */ |
|
1661
|
3 |
32 |
if (n <= 2) return n; |
|
1664
|
4 |
28 |
if (kronecker_uu(2,n) == -1) return 2; |
|
1666
|
3 |
25 |
if (is_prime(n)) { |
|
1667
|
31 |
0 |
for (a = 3; a < n; a += 2) |
|
1668
|
3 |
28 |
if (kronecker_uu(a,n) == -1) |
|
1678
|
22 |
3 |
if (!(n&1)) { /* Check and remove all multiples of 2 */ |
|
1679
|
22 |
0 |
int e = ctz(n); |
|
1681
|
4 |
18 |
if (e >= 2 || n == 1) return 2; |
|
|
0 |
4 |
if (e >= 2 || n == 1) return 2; |
|
1683
|
4 |
3 |
if (!(n % 3) || !(n % 5) || !(n % 11) || !(n % 13) || !(n % 19)) return 2; |
|
|
2 |
2 |
if (!(n % 3) || !(n % 5) || !(n % 11) || !(n % 13) || !(n % 19)) return 2; |
|
|
2 |
0 |
if (!(n % 3) || !(n % 5) || !(n % 11) || !(n % 13) || !(n % 19)) return 2; |
|
|
2 |
0 |
if (!(n % 3) || !(n % 5) || !(n % 11) || !(n % 13) || !(n % 19)) return 2; |
|
|
0 |
2 |
if (!(n % 3) || !(n % 5) || !(n % 11) || !(n % 13) || !(n % 19)) return 2; |
|
1685
|
4 |
0 |
for (a = 2; a < n; a = next_prime(a)) { |
|
1686
|
6 |
2 |
for (i = 0; i < nf.nfactors; i++) |
|
1687
|
6 |
0 |
if (a < nf.f[i] && kronecker_uu(a,nf.f[i]) == -1) |
|
|
2 |
4 |
if (a < nf.f[i] && kronecker_uu(a,nf.f[i]) == -1) |
|
1696
|
0 |
94 |
if (n == 0) return (a == 1); /* Should return undef */ |
|
1697
|
6 |
88 |
if (n <= 2) return 1; |
|
1698
|
0 |
88 |
if (a >= n) a %= n; |
|
1699
|
30 |
58 |
if (a <= 1) return 1; |
|
1701
|
3 |
55 |
if (is_prob_prime(n)) { |
|
1708
|
97 |
38 |
for (i = 0, res = 1; res && i < nf.nfactors; i++) { |
|
|
80 |
17 |
for (i = 0, res = 1; res && i < nf.nfactors; i++) { |
|
1709
|
60 |
20 |
if (nf.e[i] == 1 && (nf.f[i] == 2 || gcd_ui(a,nf.f[i]) != 1)) |
|
|
53 |
7 |
if (nf.e[i] == 1 && (nf.f[i] == 2 || gcd_ui(a,nf.f[i]) != 1)) |
|
|
13 |
40 |
if (nf.e[i] == 1 && (nf.f[i] == 2 || gcd_ui(a,nf.f[i]) != 1)) |
|
1711
|
20 |
40 |
else if (nf.e[i] == 1 || (nf.f[i] != 2 && gcd_ui(a,nf.f[i]) == 1)) |
|
|
15 |
5 |
else if (nf.e[i] == 1 || (nf.f[i] != 2 && gcd_ui(a,nf.f[i]) == 1)) |
|
|
11 |
4 |
else if (nf.e[i] == 1 || (nf.f[i] != 2 && gcd_ui(a,nf.f[i]) == 1)) |
|
1726
|
0 |
75 |
if (n <= 1) return n; /* znorder(x,0) = 0, znorder(x,1) = 1 */ |
|
1727
|
3 |
72 |
if (a <= 1) return a; /* znorder(0,x) = 0, znorder(1,x) = 1 (x > 1) */ |
|
1728
|
6 |
66 |
if (gcd_ui(a,n) > 1) return 0; |
|
1735
|
60 |
6 |
if (n & 1) { |
|
1738
|
224 |
60 |
for (i = 0; i < phif.nfactors; i++) { |
|
1743
|
209 |
224 |
for (ek = 0; a1 != mont1 && ek++ <= ei; a1 = mont_powmod(a1, pi, n)) |
|
|
209 |
0 |
for (ek = 0; a1 != mont1 && ek++ <= ei; a1 = mont_powmod(a1, pi, n)) |
|
1745
|
0 |
224 |
if (ek > ei) return 0; |
|
1749
|
7 |
6 |
for (i = 0; i < phif.nfactors; i++) { |
|
1754
|
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)) |
|
1756
|
0 |
7 |
if (ek > ei) return 0; |
|
1768
|
4 |
24 |
if (n <= 4) return (n == 0) ? 0 : n-1; |
|
|
4 |
0 |
if (n <= 4) return (n == 0) ? 0 : n-1; |
|
1769
|
1 |
23 |
if (n % 4 == 0) return 0; |
|
1772
|
5 |
18 |
if (isneven) n >>= 1; |
|
1775
|
5 |
18 |
p = ispow ? root : n; |
|
1776
|
2 |
21 |
if (p == 3 && isneven) return 5; |
|
|
1 |
1 |
if (p == 3 && isneven) return 5; |
|
1777
|
2 |
20 |
if (!is_prob_prime(p)) return 0; |
|
1780
|
5 |
15 |
psquared = ispow ? p*p : 0; |
|
1783
|
58 |
20 |
for (i = 1; i < phif.nfactors; i++) |
|
1790
|
918 |
0 |
for (a = 2; a < p; a++) { |
|
1791
|
60 |
858 |
if (isneven && !(a&1)) continue; |
|
|
30 |
30 |
if (isneven && !(a&1)) continue; |
|
1792
|
877 |
11 |
if (a == 4 || a == 8 || a == 9) continue; /* Skip some perfect powers */ |
|
|
869 |
8 |
if (a == 4 || a == 8 || a == 9) continue; /* Skip some perfect powers */ |
|
|
11 |
858 |
if (a == 4 || a == 8 || a == 9) continue; /* Skip some perfect powers */ |
|
1793
|
687 |
171 |
if (kronecker_uu(a, p) != -1) continue; |
|
1795
|
278 |
20 |
for (i = 1; i < phif.nfactors; i++) |
|
1796
|
151 |
127 |
if (mont_powmod(r, phi_div_fac[i], p) == mont1) |
|
1798
|
20 |
151 |
if (i == phif.nfactors) |
|
1799
|
5 |
15 |
if (!ispow || powmod(a, phi, psquared) != 1) |
|
|
5 |
0 |
if (!ispow || powmod(a, phi, psquared) != 1) |
|
1826
|
1 |
84 |
if (n <= 1) return n; |
|
1827
|
53 |
31 |
if (a >= n) a %= n; |
|
1828
|
1 |
83 |
if (a == 0) return (n == 1); |
|
1829
|
13 |
70 |
if (a == 1) return (n <= 2); |
|
1830
|
5 |
65 |
if (n <= 4) return a == n-1; |
|
1831
|
1 |
64 |
if (n % 4 == 0) return 0; |
|
1833
|
5 |
59 |
if (!(n&1)) { /* If n is even, */ |
|
1834
|
0 |
5 |
if (!(a&1)) return 0; /* 'a' cannot also be even */ |
|
1838
|
11 |
53 |
if (is_perfect_square(a)) return 0; |
|
1839
|
0 |
53 |
if (gcd_ui(a,n) != 1) return 0; |
|
1841
|
25 |
28 |
if (!nprime) { |
|
1843
|
2 |
23 |
if (!k) return 0; /* Not a prime power */ |
|
1846
|
5 |
18 |
if (k > 1 && powmod(a, p-1, p*p) == 1) return 0; |
|
|
0 |
5 |
if (k > 1 && powmod(a, p-1, p*p) == 1) return 0; |
|
1848
|
10 |
41 |
if (kronecker_uu(a,n) != -1) return 0; |
|
1854
|
1 |
40 |
if (is_power(a,3) && gcd_ui(3,phi) != 1) return 0; |
|
|
0 |
1 |
if (is_power(a,3) && gcd_ui(3,phi) != 1) return 0; |
|
1857
|
41 |
0 |
if (n & 1) { |
|
1861
|
41 |
0 |
if ((phi % 2) == 0 && mont_powmod(a, phi/2, n) == mont1) return 0; |
|
|
0 |
41 |
if ((phi % 2) == 0 && mont_powmod(a, phi/2, n) == mont1) return 0; |
|
1862
|
17 |
24 |
if ((phi % 3) == 0 && mont_powmod(a, phi/3, n) == mont1) return 0; |
|
|
5 |
12 |
if ((phi % 3) == 0 && mont_powmod(a, phi/3, n) == mont1) return 0; |
|
1863
|
19 |
17 |
if ((phi % 5) == 0 && mont_powmod(a, phi/5, n) == mont1) return 0; |
|
|
2 |
17 |
if ((phi % 5) == 0 && mont_powmod(a, phi/5, n) == mont1) return 0; |
|
1865
|
102 |
33 |
for (i = 0; i < phif.nfactors; i++) |
|
1866
|
39 |
63 |
if (phif.f[i] > 5 && mont_powmod(a, phi/phif.f[i], n) == mont1) |
|
|
1 |
38 |
if (phif.f[i] > 5 && mont_powmod(a, phi/phif.f[i], n) == mont1) |
|
1872
|
0 |
0 |
if ((phi % 2) == 0 && powmod(a, phi/2, n) == 1) return 0; |
|
|
0 |
0 |
if ((phi % 2) == 0 && powmod(a, phi/2, n) == 1) return 0; |
|
1873
|
0 |
0 |
if ((phi % 3) == 0 && powmod(a, phi/3, n) == 1) return 0; |
|
|
0 |
0 |
if ((phi % 3) == 0 && powmod(a, phi/3, n) == 1) return 0; |
|
1874
|
0 |
0 |
if ((phi % 5) == 0 && powmod(a, phi/5, n) == 1) return 0; |
|
|
0 |
0 |
if ((phi % 5) == 0 && powmod(a, phi/5, n) == 1) return 0; |
|
1877
|
0 |
0 |
for (i = 0; i < phif.nfactors; i++) |
|
1878
|
0 |
0 |
if (phif.f[i] > 5 && powmod(a, phi/phif.f[i], n) == 1) |
|
|
0 |
0 |
if (phif.f[i] > 5 && powmod(a, phi/phif.f[i], n) == 1) |
|
1888
|
13 |
9618 |
if (a == 0 && b == 0) { olds = 0; t = 0; } |
|
|
1 |
12 |
if (a == 0 && b == 0) { olds = 0; t = 0; } |
|
1889
|
23281 |
9631 |
while (r != 0) { |
|
1895
|
4 |
9627 |
if (oldr < 0) /* correct sign */ |
|
1897
|
9631 |
0 |
if (u != 0) *u = olds; |
|
1898
|
8692 |
939 |
if (v != 0) *v = oldt; |
|
1899
|
8680 |
951 |
if (cs != 0) *cs = s; |
|
1900
|
8680 |
951 |
if (ct != 0) *ct = t; |
|
1908
|
111180 |
52385 |
while (nr != 0) { |
|
1913
|
6805 |
45580 |
if (r > 1) return 0; /* No inverse */ |
|
1914
|
18008 |
27572 |
if (t < 0) t += n; |
|
1920
|
65 |
24978 |
if (binv == 0) return 0; |
|
1926
|
0 |
71 |
if (binv == 0) return 0; |
|
1944
|
15 |
0 |
if (Q) *Q=q; |
|
1945
|
15 |
0 |
if (R) *R=r; |
|
1951
|
4 |
17 |
if ((r > 0 && d < 0) || (r < 0 && d > 0)) { q--; r += d; } |
|
|
0 |
4 |
if ((r > 0 && d < 0) || (r < 0 && d > 0)) { q--; r += d; } |
|
|
13 |
4 |
if ((r > 0 && d < 0) || (r < 0 && d > 0)) { q--; r += d; } |
|
|
8 |
5 |
if ((r > 0 && d < 0) || (r < 0 && d > 0)) { q--; r += d; } |
|
1952
|
21 |
0 |
if (Q) *Q=q; |
|
1953
|
21 |
0 |
if (R) *R=r; |
|
1959
|
17 |
1 |
if (r != 0 && ((D >= 0) == (d >= 0))) { q++; r -= d; } |
|
|
5 |
12 |
if (r != 0 && ((D >= 0) == (d >= 0))) { q++; r -= d; } |
|
1960
|
18 |
0 |
if (Q) *Q=q; |
|
1961
|
18 |
0 |
if (R) *R=r; |
|
1967
|
13 |
5 |
if (r < 0) { |
|
1968
|
8 |
5 |
if (d > 0) { q--; r += d; } |
|
1971
|
18 |
0 |
if (Q) *Q=q; |
|
1972
|
18 |
0 |
if (R) *R=r; |
|
1977
|
0 |
26528 |
if (n <= 1) return 0; |
|
1978
|
28 |
26500 |
if (a >= 0) { |
|
1982
|
26497 |
3 |
return (r == 0) ? 0 : n-r; |
|
2002
|
511 |
379 |
do { td/=p; e += td; } while (td > 0); |
|
2009
|
225 |
0 |
if (n < 1000) { |
|
2011
|
2011 |
20 |
for (i = 2; i <= n && res != 0; i++) |
|
|
1806 |
205 |
for (i = 2; i <= n && res != 0; i++) |
|
2021
|
0 |
0 |
for (i = 1; i <= 3; i++) { /* Handle 2,3,5 assume n>=25*/ |
|
2025
|
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)) { |
|
2026
|
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 ) |
|
2027
|
0 |
0 |
if (p <= nsqn) { |
|
2030
|
0 |
0 |
while (p > nhi) { |
|
2037
|
0 |
0 |
if (p >= nlo) |
|
2040
|
0 |
0 |
if (res == 0) break; |
|
2056
|
196 |
2 |
if (n < 1000) { |
|
2058
|
1746 |
82 |
for (i = 2; i <= n && res != 0; i++) { |
|
|
1632 |
114 |
for (i = 2; i <= n && res != 0; i++) { |
|
2060
|
0 |
1632 |
res = mont_mulmod(res,monti,m); |
|
2071
|
6 |
2 |
for (i = 1; i <= 3; i++) { /* Handle 2,3,5 assume n>=25*/ |
|
2074
|
0 |
6 |
res = mont_mulmod(res, mont_powmod(mp,_powersin(p,n),m), m); |
|
2076
|
9 |
0 |
while (res!=0 && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
|
7 |
2 |
while (res!=0 && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
2077
|
353642 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
2 |
353640 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
353640 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
353642 |
21041 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
21043 |
7 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
2079
|
373 |
353267 |
if (p <= nsqn) { |
|
2080
|
0 |
373 |
res = mont_mulmod(res, mont_powmod(mp,_powersin(p,n),m), m); |
|
2082
|
2457 |
353267 |
while (p > nhi) { |
|
2083
|
0 |
2457 |
res = mont_mulmod(res, mont_powmod(s1,j,m), m); |
|
2089
|
353267 |
0 |
if (p >= nlo) |
|
2090
|
0 |
353267 |
s1 = mont_mulmod(s1, mp, m); |
|
2092
|
0 |
353640 |
if (res == 0) break; |
|
2096
|
0 |
2 |
res = mont_mulmod(res, s1, m); |
|
2100
|
0 |
198 |
res = mont_recover(res, m); |
|
2110
|
822 |
0 |
if (n >= m || m == 1) return 0; |
|
|
0 |
822 |
if (n >= m || m == 1) return 0; |
|
2111
|
744 |
78 |
if (n <= 1 || m == 2) return (n <= 1); |
|
|
0 |
744 |
if (n <= 1 || m == 2) return (n <= 1); |
|
2113
|
306 |
438 |
if (n <= 10) { /* Keep things simple for small n */ |
|
2114
|
1358 |
236 |
for (i = 2; i <= n && res != 0; i++) |
|
|
1288 |
70 |
for (i = 2; i <= n && res != 0; i++) |
|
2120
|
336 |
102 |
if (n > m/2 && m_prime) /* Check if we can go backwards */ |
|
|
74 |
262 |
if (n > m/2 && m_prime) /* Check if we can go backwards */ |
|
2122
|
14 |
424 |
if (d < 2) |
|
2123
|
7 |
7 |
return (d == 0) ? m-1 : 1; /* Wilson's Theorem: n = m-1 and n = m-2 */ |
|
2125
|
3 |
421 |
if (d > 100 && !m_prime) { /* Check for composite m that leads to 0 */ |
|
|
2 |
1 |
if (d > 100 && !m_prime) { /* Check for composite m that leads to 0 */ |
|
2128
|
6 |
2 |
for (i = 0; i < mf.nfactors; i++) { |
|
2130
|
4 |
2 |
if (t > maxpk) |
|
2134
|
1 |
1 |
if (n >= maxpk) |
|
2139
|
198 |
225 |
if (m & 1) { |
|
2147
|
60 |
363 |
if (d != n && res != 0) { /* Handle backwards case */ |
|
|
60 |
0 |
if (d != n && res != 0) { /* Handle backwards case */ |
|
2148
|
31 |
29 |
if (!(d&1)) res = submod(m,res,m); |
|
2162
|
0 |
29013 |
while (n >= p) { |
|
2173
|
68818 |
0 |
MPUassert(p >= 2 && m >= p && (m % p) == 0, "_factorialmod called with wrong args"); |
|
|
68818 |
0 |
MPUassert(p >= 2 && m >= p && (m % p) == 0, "_factorialmod called with wrong args"); |
|
|
0 |
68818 |
MPUassert(p >= 2 && m >= p && (m % p) == 0, "_factorialmod called with wrong args"); |
|
2174
|
42312 |
26506 |
if (n <= 1) return 1; |
|
2176
|
0 |
26506 |
if (n >= m) { |
|
2178
|
0 |
0 |
if ( ((n/m) & 1) && (p > 2 || m == 4) ) r = m-1; |
|
|
0 |
0 |
if ( ((n/m) & 1) && (p > 2 || m == 4) ) r = m-1; |
|
|
0 |
0 |
if ( ((n/m) & 1) && (p > 2 || m == 4) ) r = m-1; |
|
2183
|
13299 |
13207 |
if (m & 1) { |
|
2187
|
360971 |
13299 |
for (i = pmod = 2; i <= n; i++) { |
|
2189
|
9654 |
351317 |
if (pmod++ == p) pmod = 1; |
|
2190
|
0 |
351317 |
else r = mont_mulmod(r, mi, m); |
|
2192
|
0 |
13299 |
r = mont_recover(r, m); |
|
2196
|
33505 |
13207 |
for (i = pmod = 2; i <= n; i++) { |
|
2197
|
20554 |
12951 |
if (pmod++ == p) pmod = 1; |
|
2206
|
2995 |
2995 |
for (ip = n; ip > 1; ip /= p) |
|
2214
|
9645 |
30104 |
if (k > n) return 0; |
|
2215
|
16208 |
13896 |
if (k == 0 || k == n) return 1; |
|
|
6537 |
9671 |
if (k == 0 || k == n) return 1; |
|
2216
|
2961 |
6710 |
if (k > n/2) k = n-k; |
|
2219
|
0 |
9671 |
if (e <= b) return 0; |
|
2222
|
6676 |
2995 |
if (k == 1) return n % m; |
|
2226
|
0 |
2995 |
if (k >= m) { |
|
2232
|
2995 |
0 |
if (m & 1) { |
|
2235
|
77769 |
2995 |
for (i = n-k+1, ires = (i-1)%p; i <= n; i++) { |
|
2237
|
0 |
77769 |
if (++ires == p) { ires = 0; do { ip /= p; } while ((ip % p) == 0); } |
|
|
0 |
0 |
if (++ires == p) { ires = 0; do { ip /= p; } while ((ip % p) == 0); } |
|
2238
|
0 |
77769 |
num = mont_mulmod(num, mont_geta(ip, m), m); |
|
2240
|
0 |
2995 |
num = mont_recover(num, m); |
|
2245
|
0 |
0 |
for (i = n-k+1, ires = (i-1) % p; i <= n; i++) { |
|
2247
|
0 |
0 |
if (++ires == p) { ires = 0; do { ip /= p; } while ((ip % p) == 0); } |
|
|
0 |
0 |
if (++ires == p) { ires = 0; do { ip /= p; } while ((ip % p) == 0); } |
|
2254
|
0 |
2995 |
if (b > 0) r = mulmod(r, ipow(p,b), m); |
|
2262
|
0 |
20303 |
if (p < 2) return 0; |
|
2263
|
4681 |
15622 |
if (p == 2) return !(~n & k); |
|
2265
|
39749 |
15622 |
for (t = n, ln = 0; t > 0; t /= p) |
|
2267
|
30388 |
15622 |
for (t = k, lk = 0; t > 0; t /= p) |
|
2271
|
39749 |
15622 |
for (i = ln-1; i >= 0; i--) { |
|
2273
|
30388 |
9361 |
UV ki = (i < lk) ? vk[i] : 0; |
|
2286
|
0 |
7812 |
MPUassert(q < BITS_PER_WORD, "bad exponent in binomialmod generalized lucas"); |
|
2291
|
34999 |
7812 |
for (d = 0; n1 > 0; d++) { |
|
2297
|
34999 |
7812 |
for (i = 0; i < d; i++) |
|
2298
|
27187 |
7812 |
e[i] = (N[i] < (K[i] + ((i > 0) ? e[i-1] : 0))); |
|
2300
|
27187 |
7812 |
for (i = d-1; i >= 1; i--) |
|
2303
|
2607 |
5205 |
if (e[0] >= q) return 0; |
|
2309
|
21941 |
5205 |
for (d = 0; n1 > 0; d++) { |
|
2316
|
2837 |
2368 |
res = ((p > 2 || q < 3) && q < d && e[q-1] % 2) ? m-1 : 1; |
|
|
2022 |
815 |
res = ((p > 2 || q < 3) && q < d && e[q-1] % 2) ? m-1 : 1; |
|
|
3992 |
398 |
res = ((p > 2 || q < 3) && q < d && e[q-1] % 2) ? m-1 : 1; |
|
|
1847 |
2145 |
res = ((p > 2 || q < 3) && q < d && e[q-1] % 2) ? m-1 : 1; |
|
2320
|
21941 |
5205 |
for (i = 0; i < d; i++) { |
|
2332
|
0 |
21344 |
if (m <= 1) { *res = 0; return 1; } |
|
2333
|
21342 |
2 |
if (k == 0 || k >= n) { *res = (k == 0 || k == n); return 1; } |
|
|
1040 |
20302 |
if (k == 0 || k >= n) { *res = (k == 0 || k == n); return 1; } |
|
|
1040 |
2 |
if (k == 0 || k >= n) { *res = (k == 0 || k == n); return 1; } |
|
|
1040 |
0 |
if (k == 0 || k >= n) { *res = (k == 0 || k == n); return 1; } |
|
2335
|
780 |
19522 |
if (m == 2) { *res = !(~n & k); return 1; } |
|
2342
|
6247 |
13275 |
if (is_prime(m)) { |
|
2351
|
21868 |
13275 |
for (i = 0; i < mf.nfactors; i++) { |
|
2352
|
14056 |
7812 |
if (mf.e[i] == 1) { |
|
2373
|
0 |
342 |
if (e == 0) return 1; |
|
2374
|
93 |
249 |
if (p == 2) return 3UL << (e-1); |
|
2375
|
61 |
188 |
if (p == 3) k = 8; |
|
2376
|
39 |
149 |
else if (p == 5) k = 20; |
|
2377
|
26 |
123 |
else if (p == 7) k = 16; |
|
2378
|
120 |
3 |
else if (p < 300) { /* Simple search */ |
|
2381
|
7336 |
276 |
while (!(a == 0 && b == 1)) { |
|
|
156 |
120 |
while (!(a == 0 && b == 1)) { |
|
2391
|
10 |
3 |
for (i = 0; i < kf.nfactors; i++) { |
|
2392
|
11 |
5 |
for (j = 0; j < kf.e[i]; j++) { |
|
2393
|
5 |
6 |
if (lucasumod(1, p-1, k/kf.f[i], p) != 0) break; |
|
2398
|
36 |
213 |
return (e == 1) ? k : k * ipow(p, e-1); |
|
2406
|
2 |
185 |
if (n <= 1) return (n == 1); |
|
2409
|
342 |
184 |
for (i = 0, k = 1; i < nf.nfactors; i++) { |
|
2411
|
1 |
341 |
if (k == 0) return 0; |
|
2416
|
184 |
0 |
lim = (UV_MAX/6 < n) ? UV_MAX : 6*n; |
|
2419
|
184 |
4 |
if (lucasumod(1, n-1, r-1, n) == 1) |
|
2421
|
4 |
0 |
} while (r <= (lim-k)); |
|
2432
|
131600 |
49246 |
while (n) { |
|
2447
|
2879 |
924 |
while (n) { |
|
2459
|
3857 |
1117 |
if (base == 10 && exponent == 2) { |
|
|
856 |
3001 |
if (base == 10 && exponent == 2) { |
|
2461
|
924 |
856 |
for (h = 0; n > 100; h++) |
|
2463
|
242 |
614 |
return (sh[n] == 0) ? 0 : h+sh[n]; |
|
2466
|
53134 |
230 |
for (h = 1; n > 1 && n != ncheck; h++) { |
|
|
49246 |
3888 |
for (h = 1; n > 1 && n != ncheck; h++) { |
|
2467
|
16460 |
32786 |
if ((h & (h-1)) == 0) ncheck = n; /* Brent cycle finding */ |
|
2471
|
225 |
3893 |
return (n == 1) ? h : 0; |
|
2485
|
0 |
14 |
if (num == 0) { *r = 0; if (mod) *mod = 0; return 1; } /* Dubious return */ |
|
|
0 |
0 |
if (num == 0) { *r = 0; if (mod) *mod = 0; return 1; } /* Dubious return */ |
|
2487
|
33 |
2 |
for (i = 0; i < num; i++) { |
|
2490
|
6 |
27 |
if (gcd != 1) return 0; /* not coprime */ |
|
2492
|
6 |
21 |
if (ni > (UV_MAX/lcm)) return 0; /* lcm overflow */ |
|
2495
|
8 |
2 |
for (i = 0; i < num; i++) { |
|
2499
|
0 |
8 |
if (inverse == 0) return 0; /* n's coprime so should never happen */ |
|
2504
|
2 |
0 |
if (mod) *mod = lcm; |
|
2512
|
2 |
13349 |
if (num == 0) { *r = 0; if (mod) *mod = 0; return 1; } /* Dubious return */ |
|
|
2 |
0 |
if (num == 0) { *r = 0; if (mod) *mod = 0; return 1; } /* Dubious return */ |
|
2515
|
146839 |
13349 |
for (gi = 0, gap = sgaps[gi]; gap >= 1; gap = sgaps[++gi]) { |
|
2516
|
8687 |
146839 |
for (i = gap; i < num; i++) { |
|
2518
|
8726 |
7097 |
for (j = i; j >= gap && n[j-gap] < tn; j -= gap) |
|
|
7136 |
1590 |
for (j = i; j >= gap && n[j-gap] < tn; j -= gap) |
|
2524
|
0 |
13349 |
if (n[num-1] == 0) return -1; /* mod 0 */ |
|
2525
|
2 |
13347 |
if (n[0] > IV_MAX) return _simple_chinese(r,mod,a,n,num); |
|
2527
|
8680 |
13331 |
for (i = 1; i < num; i++) { |
|
2531
|
14 |
8666 |
if (gcd != 1 && ((sum % gcd) != (a[i] % gcd))) return -1; |
|
|
4 |
10 |
if (gcd != 1 && ((sum % gcd) != (a[i] % gcd))) return -1; |
|
2532
|
7072 |
1604 |
if (s < 0) s = -s; |
|
2533
|
1604 |
7072 |
if (t < 0) t = -t; |
|
2534
|
12 |
8664 |
if (s > (IV)(IV_MAX/lcm)) return _simple_chinese(r,mod,a,n,num); |
|
2536
|
1599 |
7065 |
if (u < 0) u += lcm; |
|
2537
|
7063 |
1601 |
if (v < 0) v += lcm; |
|
2543
|
38 |
13293 |
if (mod) *mod = lcm; |
|
2548
|
0 |
487 |
if (n == 0) return 0; |
|
2549
|
40 |
447 |
if (kstatus < 0) { |
|
2550
|
38 |
2 |
if (*a != 0) *a = modinverse(*a, n); |
|
2551
|
19 |
21 |
if (*a == 0) return 0; |
|
2574
|
0 |
987 |
if (digits == 0) return 0; |
|
2575
|
987 |
0 |
if (digits >= 1 && digits <= DBL_DIG && digits <= 18) { |
|
|
15 |
972 |
if (digits >= 1 && digits <= DBL_DIG && digits <= 18) { |
|
|
15 |
0 |
if (digits >= 1 && digits <= DBL_DIG && digits <= 18) { |
|
2586
|
1776026 |
972 |
for (b = 0; b < c; b++) a[b] = 2000; |
|
2589
|
125644 |
972 |
while (i < digits) { |
|
2592
|
0 |
125644 |
if (b > 107001) { /* Use 64-bit intermediate while necessary. */ |
|
2593
|
0 |
0 |
for (d64 = d; --b > 107000; ) { |
|
2602
|
148341500 |
125644 |
while (--b > 0) { |
|
2610
|
0 |
125644 |
if (d4 > 9999) { |
|
2612
|
0 |
0 |
for (b = i; out[--b] == '9';) out[b] = '0'; |
|
2622
|
480 |
492 |
if (out[digits-1] >= '5') out[digits-2]++; /* Round */ |
|
2623
|
70 |
972 |
for (i = digits-2; out[i] == '9'+1; i--) /* Keep rounding */ |
|
2636
|
338 |
0 |
if (s != 0 && len > 0) { |
|
|
338 |
0 |
if (s != 0 && len > 0) { |
|
2638
|
261 |
77 |
if (s[0] == '-' || s[0] == '+') { s++; len--; } |
|
|
0 |
261 |
if (s[0] == '-' || s[0] == '+') { s++; len--; } |
|
2639
|
338 |
8 |
while (len > 0 && *s == '0') { s++; len--; } |
|
|
8 |
330 |
while (len > 0 && *s == '0') { s++; len--; } |
|
2640
|
8 |
330 |
if (len == 0) { s--; len = 1; neg = 0; } /* value is 0 */ |
|
2641
|
7236 |
338 |
for (i = 0; i < len; i++) |
|
2642
|
0 |
7236 |
if (!isDIGIT(s[i])) |
|
2645
|
338 |
0 |
if (s == 0 || len == 0 || i < len) croak("Parameter must be an integer"); |
|
|
338 |
0 |
if (s == 0 || len == 0 || i < len) croak("Parameter must be an integer"); |
|
|
0 |
338 |
if (s == 0 || len == 0 || i < len) croak("Parameter must be an integer"); |
|
2654
|
39 |
128 |
if (aneg != bneg) return (bneg) ? 1 : -1; |
|
|
13 |
26 |
if (aneg != bneg) return (bneg) ? 1 : -1; |
|
2655
|
19 |
109 |
if (aneg) { /* swap a and b if both negative */ |
|
2659
|
78 |
50 |
if (alen != blen) return (alen > blen) ? 1 : -1; |
|
|
68 |
10 |
if (alen != blen) return (alen > blen) ? 1 : -1; |
|
2660
|
482 |
7 |
for (i = 0; i < blen; i++) |
|
2661
|
43 |
439 |
if (a[i] != b[i]) |
|
2662
|
38 |
5 |
return (a[i] > b[i]) ? 1 : -1; |
|
2678
|
2 |
2 |
if (a == 0) return 1; |
|
2681
|
2 |
0 |
if (a[0] == '-' || a[0] == '+') { a++; alen--; } |
|
|
0 |
2 |
if (a[0] == '-' || a[0] == '+') { a++; alen--; } |
|
2682
|
2 |
0 |
while (alen > 0 && *a == '0') { a++; alen--; } |
|
|
0 |
2 |
while (alen > 0 && *a == '0') { a++; alen--; } |
|
2684
|
0 |
2 |
if (aneg != bneg) return min ? (bneg == 1) : (aneg == 1); |
|
|
0 |
0 |
if (aneg != bneg) return min ? (bneg == 1) : (aneg == 1); |
|
2685
|
0 |
2 |
if (aneg == 1) min = !min; |
|
2686
|
0 |
2 |
if (alen != blen) return min ? (alen > blen) : (blen > alen); |
|
|
0 |
0 |
if (alen != blen) return min ? (alen > blen) : (blen > alen); |
|
2688
|
2 |
0 |
for (i = 0; i < blen; i++) |
|
2689
|
2 |
0 |
if (a[i] != b[i]) |
|
2690
|
1 |
1 |
return min ? (a[i] > b[i]) : (b[i] > a[i]); |
|
2700
|
17 |
0 |
if (s[0] == '-' || s[0] == '+') s++; |
|
|
0 |
17 |
if (s[0] == '-' || s[0] == '+') s++; |
|
2701
|
0 |
17 |
while (s[0] == '0') s++; |
|
2706
|
499 |
6 |
for (i = 0; i < len; i++) { |
|
2708
|
499 |
0 |
int d = !isalnum(c) ? 255 : (c <= '9') ? c-'0' : (c <= 'Z') ? c-'A'+10 : c-'a'+10; |
|
|
456 |
43 |
int d = !isalnum(c) ? 255 : (c <= '9') ? c-'0' : (c <= 'Z') ? c-'A'+10 : c-'a'+10; |
|
|
0 |
43 |
int d = !isalnum(c) ? 255 : (c <= '9') ? c-'0' : (c <= 'Z') ? c-'A'+10 : c-'a'+10; |
|
2709
|
0 |
499 |
if (d >= base) croak("Invalid digit for base %d", base); |
|
2710
|
11 |
488 |
if (n > max) return 0; /* Overflow */ |
|
2721
|
14 |
0 |
if (len < 0 || len > BITS_PER_WORD) |
|
|
0 |
14 |
if (len < 0 || len > BITS_PER_WORD) |
|
2723
|
80 |
13 |
for (i = 0; i < len; i++) { |
|
2725
|
1 |
79 |
if (n > (UV_MAX-d)/base) break; /* overflow */ |
|
2738
|
1 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
|
1 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
|
1 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
|
0 |
1 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
2740
|
0 |
1 |
if (r[0] >= (UV) base) return 0; /* TODO: We don't apply extended carry */ |
|
2744
|
1 |
0 |
if (base == 2 || base == 16) { |
|
|
1 |
0 |
if (base == 2 || base == 16) { |
|
2746
|
0 |
1 |
*s++ = (base == 2) ? 'b' : 'x'; |
|
2748
|
45 |
1 |
for (i = 0; i < len; i++) { |
|
2750
|
27 |
18 |
s[i] = (d < 10) ? '0'+(char)d : 'a'+(char)(d-10); |
|
2761
|
163 |
0 |
if (base < 2 || length > 128) return -1; |
|
|
0 |
163 |
if (base < 2 || length > 128) return -1; |
|
2763
|
153 |
10 |
if (base == 2) { |
|
2764
|
3728 |
153 |
for (d = 0; n; n >>= 1) |
|
2767
|
34 |
10 |
for (d = 0; n; n /= base) |
|
2770
|
156 |
7 |
if (length < 0) length = d; |
|
2771
|
31 |
163 |
while (d < length) |
|
2781
|
0 |
5 |
if (len < 0) return -1; |
|
2782
|
0 |
5 |
if (base > 36) croak("invalid base for string: %d", base); |
|
2784
|
30 |
5 |
for (i = 0; i < len; i++) { |
|
2786
|
29 |
1 |
s[i] = (dig < 10) ? '0'+(char)dig : 'a'+(char)(dig-10); |
|
2796
|
5 |
3 |
if (hi < 0) { |
|
2798
|
2 |
3 |
if (lo == 0) { |
|
2812
|
151 |
8 |
} while (sum); |
|
2833
|
79 |
8 |
for (i=0; i < slen/2; i++) { |
|
2839
|
5 |
3 |
if (isneg) { |
|
2840
|
99 |
5 |
for (i = slen; i > 0; i--) |
|
2863
|
0 |
27 |
if (str == 0) |
|
2865
|
1 |
26 |
if (str[0] != '1') |
|
2866
|
1 |
0 |
return (str[0] == '0' && str[1] == '\0'); |
|
|
1 |
0 |
return (str[0] == '0' && str[1] == '\0'); |
|
2868
|
371 |
26 |
for (i = 1; str[i] != '\0'; i++) { |
|
2869
|
104 |
267 |
if (str[i] == '1') { |
|
2870
|
0 |
104 |
if (str[i-1] == '1') |
|
2872
|
0 |
267 |
} else if (str[i] != '0') { |
|
2877
|
25 |
1 |
if (i > MAX_FIB_LEN || (i == MAX_FIB_LEN && strcmp(str, MAX_FIB_STR) > 0)) |
|
|
1 |
24 |
if (i > MAX_FIB_LEN || (i == MAX_FIB_LEN && strcmp(str, MAX_FIB_STR) > 0)) |
|
|
0 |
1 |
if (i > MAX_FIB_LEN || (i == MAX_FIB_LEN && strcmp(str, MAX_FIB_STR) > 0)) |
|
2887
|
0 |
26 |
if (str == 0) return 0; |
|
2888
|
285 |
1 |
for (len = 0; len < MAX_FIB_LEN && str[len] != '\0'; len++) |
|
|
260 |
25 |
for (len = 0; len < MAX_FIB_LEN && str[len] != '\0'; len++) |
|
2889
|
86 |
174 |
if (str[len] != '0' && str[len] != '1') |
|
|
0 |
86 |
if (str[len] != '0' && str[len] != '1') |
|
2891
|
26 |
0 |
if (len == 0 || len > MAX_FIB_LEN) return 0; |
|
|
0 |
26 |
if (len == 0 || len > MAX_FIB_LEN) return 0; |
|
2893
|
234 |
26 |
for (i = len-2; i >= 0; i--) { |
|
2895
|
77 |
157 |
if (str[i] == '1') n += fc; |
|
2907
|
1 |
26 |
if (n == 0) { |
|
2911
|
291 |
1 |
for (k = 2; k <= MAX_FIB_VAL && fc <= rn; k++) { |
|
|
266 |
25 |
for (k = 2; k <= MAX_FIB_VAL && fc <= rn; k++) { |
|
2914
|
266 |
26 |
for (i = k-1; i >= 2; i--) { |
|
2916
|
88 |
178 |
str[spos++] = '0' + (fc <= rn); |
|
2917
|
88 |
178 |
if (fc <= rn) rn -= fc; |
|
2934
|
473541 |
472642 |
while (n /= p) s += n % 2; |
|
2939
|
0 |
0 |
while (n /= p) s += n % 2; |
|
2943
|
428809 |
472642 |
if (p > a) { |
|
2946
|
472642 |
0 |
UV pow = (n <= 4294967295UL) ? _catalan_v32(a<<1,p) : _catalan_v(a<<1,p); |
|
2948
|
186211 |
286431 |
: (pow == 1) ? mulmod(m,p,n) |
|
2949
|
185962 |
249 |
: mulmod(m,powmod(p,pow,n),n); |
|
2954
|
13 |
5 |
while (n /= p) |
|
2955
|
0 |
13 |
if (n % 2) |
|
2962
|
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; |
|
2963
|
0 |
3 |
if (is_prob_prime(n)) return 1; |
|
2981
|
0 |
3 |
if (nf.nfactors == 2) { /* Conditions from Aebi and Cairns (2008) */ |
|
2982
|
0 |
0 |
if (n < UVCONST(10000000000)) return 0; /* Page 9 */ |
|
2983
|
0 |
0 |
if (2*nf.f[0]+1 >= nf.f[1]) return 0; /* Corollary 2 and 3 */ |
|
2987
|
5 |
3 |
for (i = 0; i < nf.nfactors; i++) { |
|
2988
|
0 |
5 |
if (_catalan_vtest(a << 1, nf.f[i])) |
|
3000
|
16 |
3 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
3001
|
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 ) { |
|
3007
|
1 |
2 |
return (a & 1) ? (m==(n-1)) : (m==1); |
|
3014
|
25 |
119950 |
if (x == 0) return y; |
|
3016
|
66680 |
53270 |
if (y & 1) { /* Optimize y odd */ |
|
3017
|
66680 |
0 |
x >>= ctz(x); |
|
3018
|
914688 |
66680 |
while (x != y) { |
|
3019
|
287827 |
626861 |
if (x < y) { y -= x; y >>= ctz(y); } |
|
|
287827 |
0 |
if (x < y) { y -= x; y >>= ctz(y); } |
|
3020
|
626861 |
0 |
else { x -= y; x >>= ctz(x); } |
|
3025
|
1 |
53269 |
if (y == 0) return x; |
|
3028
|
53269 |
0 |
x2 = ctz(x); |
|
3029
|
53269 |
0 |
y2 = ctz(y); |
|
3034
|
473936 |
53269 |
while (x != y) { |
|
3035
|
128159 |
345777 |
if (x < y) { |
|
3037
|
128159 |
0 |
y >>= ctz(y); |
|
3040
|
345777 |
0 |
x >>= ctz(x); |
|
3054
|
6 |
4 |
return (n < NTAU) ? tau_table[n] : 0; |
|
3061
|
3 |
398 |
if (lim*lim == b2) lim--; |
|
3062
|
42 |
359 |
if (s > lim) return 0; |
|
3064
|
334 |
25 |
if ((lim-s) < 70) { /* Iterate looking for divisors */ |
|
3065
|
6762 |
334 |
for (i = s; i <= lim; i++) |
|
3066
|
105 |
6657 |
if (b2 % i == 0) |
|
3070
|
31 |
25 |
for (i = 0; i < ndivisors && divs[i] <= lim; i++) |
|
|
31 |
0 |
for (i = 0; i < ndivisors && divs[i] <= lim; i++) |
|
3071
|
6 |
25 |
if (divs[i] >= s) |
|
3085
|
1 |
72 |
if (n == 0) return -1; |
|
3086
|
71 |
1 |
if (nmod4 == 1 || nmod4 == 2) return 0; |
|
|
1 |
70 |
if (nmod4 == 1 || nmod4 == 2) return 0; |
|
3087
|
1 |
69 |
if (n == 3) return 4; |
|
3094
|
18 |
51 |
if (b == 1) |
|
3098
|
401 |
69 |
for (; b2 = (n + b*b) >> 2, 3*b2 < n; b += 2) { |
|
3103
|
67 |
2 |
return 12*h + ((b2*3 == n) ? 4 : square && !(n&1) ? 6 : 0); |
|
|
11 |
56 |
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); |
|
3108
|
0 |
25302 |
MPUassert(k >= 3, "is_polygonal root < 3"); |
|
3110
|
48 |
25254 |
if (n <= 1) return n; |
|
3111
|
198 |
25056 |
if (k == 4) { |
|
3113
|
18 |
180 |
return is_perfect_square_ret(n,&root) ? root : 0; |
|
3115
|
108 |
24948 |
if (k == 3) { |
|
3116
|
0 |
108 |
if (n >= UV_MAX/8) *overflow = 1; |
|
3120
|
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; |
|
3124
|
0 |
25056 |
if (D+R <= D) *overflow = 1; |
|
3126
|
25056 |
0 |
if (*overflow || !is_perfect_square(D)) return 0; |
|
|
24138 |
918 |
if (*overflow || !is_perfect_square(D)) return 0; |
|
3129
|
522 |
396 |
if ((D % R) != 0) return 0; |
|
3152
|
4 |
53 |
if (n <= 3) return (n == 0) ? 1 : n; |
|
|
3 |
1 |
if (n <= 3) return (n == 0) ? 1 : n; |
|
3153
|
4 |
49 |
if (n > ((BITS_PER_WORD == 32) ? 127 : 416)) return 0; /* Overflow */ |
|
3156
|
0 |
49 |
New(0, pent, 2*d+2, UV); |
|
3159
|
245 |
49 |
for (i = 1; i <= d; i++) { |
|
3163
|
0 |
49 |
New(0, part, n+1, UV); |
|
3165
|
1626 |
49 |
for (j = 1; j <= n; j++) { |
|
3167
|
12218 |
1626 |
for (k = 1; pent[k] <= j; k++) { |
|
3168
|
6939 |
5279 |
if ((k+1) & 2) psum += part[ j - pent[k] ]; |
|
3183
|
3 |
99 |
if (n <= 2) return (n == 0) ? 1 : n; |
|
|
2 |
1 |
if (n <= 2) return (n == 0) ? 1 : n; |
|
3187
|
1186 |
0 |
for (i = 1; i < NPRIMES_TINY; i++) { |
|
3189
|
44 |
1142 |
if (p > n) break; |
|
3190
|
325 |
817 |
if (p <= sqrtn) p = ipow(p, logint(n,p)); |
|
3191
|
55 |
1087 |
if (ilcm > UV_MAX/p) return 0; |
|
3201
|
1 |
63 |
if (alen <= 1) return 0; |
|
3203
|
0 |
63 |
if (A[0] <= 1) return 0; |
|
3205
|
372 |
63 |
for (g = A[0], i = 1; i < alen; i++) |
|
3207
|
1 |
62 |
if (g != 1) croak("Frobenius number set must be coprime"); |
|
3209
|
2 |
60 |
if (UV_MAX/A[0] < A[1]) return UV_MAX; /* Overflow */ |
|
3211
|
1 |
59 |
if (alen == 2) |
|
3228
|
0 |
59 |
New(0, N, nlen+1, UV); |
|
3230
|
554245 |
59 |
for (j = 1; j < nlen; j++) |
|
3233
|
368 |
59 |
for (i = 1; i < alen; i++) { |
|
3236
|
294 |
74 |
if (np != UV_MAX && np <= ai) continue; /* Redundant basis (opt 3) */ |
|
|
64 |
230 |
if (np != UV_MAX && np <= ai) continue; /* Redundant basis (opt 3) */ |
|
3238
|
1200 |
304 |
for (r = 0; r < d; r++) { |
|
3240
|
896 |
304 |
if (r > 0) { |
|
3241
|
1064092 |
896 |
for (n = UV_MAX, q = r; q < nlen; q += d) |
|
3242
|
15454 |
1048638 |
if (N[q] < n) |
|
3245
|
884 |
316 |
if (n != UV_MAX) { |
|
3246
|
3928776 |
884 |
for (j = 0; j < (nlen / d); j++) { |
|
3249
|
2461304 |
1467472 |
if (N[p] >= n) N[p] = n; |
|
3256
|
554304 |
59 |
for (i = 0; i < nlen; i++) |
|
3257
|
554304 |
0 |
if (N[i] == UV_MAX || (N[i] != UV_MAX && N[i] > max)) |
|
|
554304 |
0 |
if (N[i] == UV_MAX || (N[i] != UV_MAX && N[i] > max)) |
|
|
33369 |
520935 |
if (N[i] == UV_MAX || (N[i] != UV_MAX && N[i] > max)) |
|
3260
|
0 |
59 |
if (max == UV_MAX) return UV_MAX; |
|
3273
|
3 |
5 |
while (f == 0) /* We can handle n! overflow if we have a valid k */ |
|
3276
|
1 |
4 |
if (k/f >= (UV)n) |
|
3279
|
45 |
5 |
for (i = 0; i < n; i++) |
|
3281
|
37 |
5 |
for (i = si; i < n-1; i++) { |
|
3285
|
19 |
18 |
if (p > 0) { |
|
3286
|
47 |
19 |
for (j = i+p, t = vec[j]; j > i; j--) |
|
3298
|
1 |
4 |
if (f == 0) return 0; |
|
3299
|
38 |
4 |
for (i = 0; i < n-1; i++) { |
|
3300
|
302 |
38 |
for (j = i+1, k = 0; j < n; j++) |
|
3301
|
137 |
165 |
if (vec[j] < vec[i]) |
|
3303
|
0 |
38 |
if ((UV)k > (UV_MAX-num)/f) return 0; /* overflow */ |
|
3324
|
0 |
73 |
if (k > n) k = n; |
|
3326
|
73 |
0 |
if (k == 0) { /* 0 of n */ |
|
3327
|
9 |
64 |
} else if (k == 1) { /* 1 of n. Pick one at random */ |
|
3329
|
23 |
41 |
} else if (k == 2 && n == 2) { /* 2 of 2. Flip a coin */ |
|
|
4 |
19 |
} else if (k == 2 && n == 2) { /* 2 of 2. Flip a coin */ |
|
3332
|
19 |
41 |
} else if (k == 2) { /* 2 of n. Pick 2 skipping dup */ |
|
3335
|
12 |
7 |
if (S[1] >= S[0]) S[1]++; |
|
3336
|
4 |
37 |
} else if (k < n/100 && k < 30) { /* k of n. Pick k with loop */ |
|
|
2 |
2 |
} else if (k < n/100 && k < 30) { /* k of n. Pick k with loop */ |
|
3337
|
20 |
2 |
for (i = 0; i < k; i++) { |
|
3340
|
90 |
20 |
for (j = 0; j < i; j++) |
|
3341
|
0 |
90 |
if (S[j] == S[i]) |
|
3343
|
0 |
20 |
} while (j < i); |
|
3345
|
2 |
37 |
} else if (k < n/100 && n > 1000000) {/* k of n. Pick k with dedup retry */ |
|
|
2 |
0 |
} else if (k < n/100 && n > 1000000) {/* k of n. Pick k with dedup retry */ |
|
3346
|
2 |
2 |
for (j = 0; j < k; ) { |
|
3347
|
74 |
2 |
for (i = j; i < k; i++) /* Fill S[j .. k-1] then sort S */ |
|
3350
|
72 |
2 |
for (j = 0, i = 1; i < k; i++) /* Find and remove dups. O(n). */ |
|
3351
|
72 |
0 |
if (S[j] != S[i]) |
|
3356
|
74 |
2 |
for (i = 0; i < k; i++) { |
|
3360
|
17 |
20 |
} else if (k < n/4) { /* k of n. Pick k with mask */ |
|
3362
|
17 |
0 |
if (n <= 32*8) mask = smask; |
|
3363
|
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); |
|
3364
|
100 |
17 |
for (i = 0; i < k; i++) { |
|
3367
|
0 |
100 |
} while ( mask[j>>5] & (1U << (j&0x1F)) ); |
|
3371
|
0 |
17 |
if (mask != smask) Safefree(mask); |
|
3372
|
2 |
18 |
} else if (k < n) { /* k of n. FYK shuffle n, pick k */ |
|
3374
|
0 |
2 |
New(0, T, n, UV); |
|
3375
|
60 |
2 |
for (i = 0; i < n; i++) |
|
3377
|
24 |
2 |
for (i = 0; i < k && i <= n-2; i++) { |
|
|
24 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
3384
|
316 |
18 |
for (i = 0; i < n; i++) |
|
3386
|
316 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
|
298 |
18 |
for (i = 0; i < k && i <= n-2; i++) { |
|
3406
|
56 |
534 |
if (n <= 1) return 1; /* (0,k) = 1, (1,k) = 1 */ |
|
3407
|
76 |
458 |
if (k <= 1) return 0; /* (n,0) = (n,1) = 0 if n > 1 */ |
|
3408
|
158 |
300 |
if (n <= k) return 1; |
|
3410
|
36 |
264 |
if (k == 2) return ((n & (n-1)) == 0); |
|
3411
|
344 |
12 |
while (n > 1 && !(n&1)) n >>= 1; |
|
|
92 |
252 |
while (n > 1 && !(n&1)) n >>= 1; |
|
3412
|
44 |
220 |
if (n <= k) return 1; |
|
3415
|
16 |
204 |
SMOOTH_TEST(n, k, 3, 5); /* after this, k >= 5, n > 3*3 */ |
|
|
12 |
192 |
SMOOTH_TEST(n, k, 3, 5); /* after this, k >= 5, n > 3*3 */ |
|
|
12 |
12 |
SMOOTH_TEST(n, k, 3, 5); /* after this, k >= 5, n > 3*3 */ |
|
|
12 |
0 |
SMOOTH_TEST(n, k, 3, 5); /* after this, k >= 5, n > 3*3 */ |
|
|
36 |
156 |
SMOOTH_TEST(n, k, 3, 5); /* after this, k >= 5, n > 3*3 */ |
|
3416
|
10 |
146 |
SMOOTH_TEST(n, k, 5, 7); /* after this, k >= 7, n > 5*5 */ |
|
|
1 |
145 |
SMOOTH_TEST(n, k, 5, 7); /* after this, k >= 7, n > 5*5 */ |
|
|
5 |
1 |
SMOOTH_TEST(n, k, 5, 7); /* after this, k >= 7, n > 5*5 */ |
|
|
1 |
0 |
SMOOTH_TEST(n, k, 5, 7); /* after this, k >= 7, n > 5*5 */ |
|
|
32 |
113 |
SMOOTH_TEST(n, k, 5, 7); /* after this, k >= 7, n > 5*5 */ |
|
3417
|
0 |
113 |
SMOOTH_TEST(n, k, 7, 11); /* after this, k >= 11, n > 7*7 */ |
|
|
0 |
113 |
SMOOTH_TEST(n, k, 7, 11); /* after this, k >= 11, n > 7*7 */ |
|
|
0 |
0 |
SMOOTH_TEST(n, k, 7, 11); /* after this, k >= 11, n > 7*7 */ |
|
|
0 |
0 |
SMOOTH_TEST(n, k, 7, 11); /* after this, k >= 11, n > 7*7 */ |
|
|
48 |
65 |
SMOOTH_TEST(n, k, 7, 11); /* after this, k >= 11, n > 7*7 */ |
|
3420
|
192 |
0 |
for (i = 5, pn = primes_tiny[i]; i < NPRIMES_TINY-1; i++) { |
|
3422
|
33 |
159 |
SMOOTH_TEST(n, k, p, pn); |
|
|
45 |
114 |
SMOOTH_TEST(n, k, p, pn); |
|
|
0 |
45 |
SMOOTH_TEST(n, k, p, pn); |
|
|
0 |
45 |
SMOOTH_TEST(n, k, p, pn); |
|
|
32 |
127 |
SMOOTH_TEST(n, k, p, pn); |
|
3424
|
0 |
0 |
if (k < pn || n < pn*pn) return (n <= k); /* k >= 503 and n >= 503*503. */ |
|
|
0 |
0 |
if (k < pn || n < pn*pn) return (n <= k); /* k >= 503 and n >= 503*503. */ |
|
3426
|
0 |
0 |
if (is_prime(n)) return 0; |
|
3427
|
0 |
0 |
if (k <= 290000) { |
|
3435
|
0 |
0 |
if (k < pn || n < pn*pn) return (n <= k); /* k > 290k, n > 25M */ |
|
|
0 |
0 |
if (k < pn || n < pn*pn) return (n <= k); /* k > 290k, n > 25M */ |
|
3448
|
28 |
2175 |
if (n == 0) return (k == 0); |
|
3449
|
28 |
2147 |
if (n == 1) return 1; |
|
3451
|
76 |
2071 |
if (k <= 1) return 1; |
|
3452
|
42 |
2029 |
if (k == 2) return (n >= 1); |
|
3453
|
45 |
1984 |
if (k == 3) return (n > 1 && (n&1)); |
|
|
45 |
0 |
if (k == 3) return (n > 1 && (n&1)); |
|
|
31 |
14 |
if (k == 3) return (n > 1 && (n&1)); |
|
3456
|
920 |
1064 |
if (!(n&1)) return 0; |
|
3457
|
308 |
756 |
if (!(n%3)) return 0; |
|
3458
|
79 |
677 |
if (k <= 5) return 1; |
|
3459
|
112 |
565 |
if (!(n%5)) return 0; |
|
3461
|
560 |
5 |
if (k <= 2500) { |
|
3470
|
1 |
4 |
if (nfac > 1 && fac[nfac-2] <= k) return 0; |
|
|
1 |
0 |
if (nfac > 1 && fac[nfac-2] <= k) return 0; |
|
3472
|
0 |
4 |
if (n < k) return 0; |
|
3474
|
3 |
1 |
if ( (n >> 30) >= 64) { /* Arbitrarily chose 2^36 for more tests */ |
|
3475
|
1 |
2 |
if (is_prime(n)) return 1; |
|
3477
|
1 |
1 |
if (nfac > 1) { /* 2 factors, but they could be composites */ |
|
3478
|
0 |
1 |
if (fac[0] < k || fac[1] < k) return 0; |
|
|
0 |
0 |
if (fac[0] < k || fac[1] < k) return 0; |
|
3479
|
0 |
0 |
if (factorint(fac[0]).f[0] < k) return 0; |
|
3480
|
0 |
0 |
if (factorint(fac[1]).f[0] < k) return 0; |
|
3492
|
99 |
146 |
for (pke = f, fmult = 1+f; e > 1; e--) { |
|
3504
|
296 |
1 |
if (n == 0 || (n & 1)) return (n == 1); |
|
|
138 |
158 |
if (n == 0 || (n & 1)) return (n == 1); |
|
3505
|
7 |
151 |
if ((n & (n-1)) == 0) return 1; /* All powers of 2 are practical */ |
|
3507
|
108 |
43 |
if ((n % 6) && (n % 20) && (n % 28) && (n % 88) && (n % 104) && (n % 16)) |
|
|
100 |
8 |
if ((n % 6) && (n % 20) && (n % 28) && (n % 88) && (n % 104) && (n % 16)) |
|
|
95 |
5 |
if ((n % 6) && (n % 20) && (n % 28) && (n % 88) && (n % 104) && (n % 16)) |
|
|
93 |
2 |
if ((n % 6) && (n % 20) && (n % 28) && (n % 88) && (n % 104) && (n % 16)) |
|
|
91 |
2 |
if ((n % 6) && (n % 20) && (n % 28) && (n % 88) && (n % 104) && (n % 16)) |
|
|
91 |
0 |
if ((n % 6) && (n % 20) && (n % 28) && (n % 88) && (n % 104) && (n % 16)) |
|
3513
|
0 |
60 |
MPUassert(nf.f[0] == 2, "is_practical first factor must be 2"); |
|
3515
|
93 |
53 |
for (i = 1; i < nf.nfactors; i++) { |
|
3516
|
7 |
86 |
if (nf.f[i] > (1 + prod)) |
|
3525
|
0 |
1066091 |
if (b < 2) croak("is_delicate_prime base must be >= 2"); |
|
3526
|
1062629 |
3462 |
if (b == 10 && n < 100) return 0; /* All 1,2,3,4 digit inputs are false */ |
|
|
100 |
1062529 |
if (b == 10 && n < 100) return 0; /* All 1,2,3,4 digit inputs are false */ |
|
3527
|
283 |
1065708 |
if (b == 3 && n == 2) return 1; |
|
|
2 |
281 |
if (b == 3 && n == 2) return 1; |
|
3529
|
981572 |
84417 |
if (!is_prime(n)) return 0; |
|
3531
|
83009 |
1408 |
if (b == 10) { |
|
3535
|
0 |
83009 |
if (n >= ipow(10,maxd)) return -1; /* We can't check all values */ |
|
3539
|
62265 |
20744 |
if ( (dold != 1 && is_prime(n - dold + 1)) || |
|
|
50793 |
11472 |
if ( (dold != 1 && is_prime(n - dold + 1)) || |
|
|
53645 |
17892 |
if ( (dold != 1 && is_prime(n - dold + 1)) || |
|
3540
|
43654 |
9991 |
(dold != 3 && is_prime(n - dold + 3)) || |
|
|
48636 |
12910 |
(dold != 3 && is_prime(n - dold + 3)) || |
|
3541
|
39918 |
8718 |
(dold != 7 && is_prime(n - dold + 7)) || |
|
|
41530 |
11298 |
(dold != 7 && is_prime(n - dold + 7)) || |
|
3542
|
7562 |
33968 |
(dold != 9 && is_prime(n - dold + 9)) ) |
|
3546
|
52855 |
0 |
for (d = 1, digpow = 10; d <= maxd && n >= digpow; digpow *= 10, d++) { |
|
|
52822 |
33 |
for (d = 1, digpow = 10; d <= maxd && n >= digpow; digpow *= 10, d++) { |
|
3548
|
261308 |
7589 |
for (dnew = 0; dnew < 10; dnew++) |
|
3549
|
236548 |
24760 |
if (dnew != dold && is_prime(n - dold*digpow + dnew*digpow)) |
|
|
45233 |
191315 |
if (dnew != dold && is_prime(n - dold*digpow + dnew*digpow)) |
|
3553
|
60 |
1348 |
} else if (b == 2) { |
|
3556
|
30 |
30 |
if (n < 127) return 0; |
|
3557
|
30 |
0 |
for (bit = log2floor(n); bit > 0; bit--) |
|
|
120 |
10 |
for (bit = log2floor(n); bit > 0; bit--) |
|
3558
|
20 |
100 |
if (is_prime(n ^ (UVCONST(1) << bit))) |
|
3576
|
2346 |
60 |
for (bm = 1; n >= bm; bm *= b) { |
|
3579
|
2346 |
0 |
if ( ((UV_MAX/b) < bm) || ((UV_MAX-bmb) < n) ) return -1; /* overflow */ |
|
|
0 |
2346 |
if ( ((UV_MAX/b) < bm) || ((UV_MAX-bmb) < n) ) return -1; /* overflow */ |
|
3582
|
7705 |
1653 |
(n % bm) != (current % bmb); |
|
3584
|
0 |
7705 |
if (counter >= b-1) croak("is_delicate_prime overflow failure\n"); |
|
3585
|
693 |
7012 |
if (is_prime(current)) |
|
3589
|
6954 |
1058 |
for (j = 1, current = n-bm; j < b-counter; j++, current -= bm) { |
|
3590
|
595 |
6359 |
if (is_prime(current)) |
|
3604
|
5 |
111 |
if (n < 3) return 1; |
|
3606
|
103 |
111 |
while (!(n&1)) n >>= 1; /* Remove all factors of two */ |
|
3608
|
51 |
60 |
if ((n % 4) == 3) return 0; |
|
3613
|
26 |
60 |
for (i = 0; !(n % 3); n /= 3) { i++; } if ((i & 1) == 1) return 0; |
|
|
8 |
52 |
for (i = 0; !(n % 3); n /= 3) { i++; } if ((i & 1) == 1) return 0; |
|
3614
|
5 |
52 |
for (i = 0; !(n % 7); n /= 7) { i++; } if ((i & 1) == 1) return 0; |
|
|
1 |
51 |
for (i = 0; !(n % 7); n /= 7) { i++; } if ((i & 1) == 1) return 0; |
|
3615
|
1 |
51 |
for (i = 0; !(n % 11); n /= 11) { i++; } if ((i & 1) == 1) return 0; |
|
|
1 |
50 |
for (i = 0; !(n % 11); n /= 11) { i++; } if ((i & 1) == 1) return 0; |
|
3616
|
1 |
50 |
for (i = 0; !(n % 19); n /= 19) { i++; } if ((i & 1) == 1) return 0; |
|
|
1 |
49 |
for (i = 0; !(n % 19); n /= 19) { i++; } if ((i & 1) == 1) return 0; |
|
3617
|
1 |
49 |
for (i = 0; !(n % 23); n /= 23) { i++; } if ((i & 1) == 1) return 0; |
|
|
1 |
48 |
for (i = 0; !(n % 23); n /= 23) { i++; } if ((i & 1) == 1) return 0; |
|
3618
|
1 |
48 |
for (i = 0; !(n % 31); n /= 31) { i++; } if ((i & 1) == 1) return 0; |
|
|
1 |
47 |
for (i = 0; !(n % 31); n /= 31) { i++; } if ((i & 1) == 1) return 0; |
|
3621
|
34 |
46 |
for (i = 0; i < nf.nfactors; i++) |
|
3622
|
1 |
33 |
if ( (nf.f[i] % 4) == 3 && (nf.e[i] & 1) == 1 ) |
|
|
1 |
0 |
if ( (nf.f[i] % 4) == 3 && (nf.e[i] & 1) == 1 ) |
|
3630
|
79 |
40 |
return ((tz & 1) == 1) || (((n>>tz) % 8) != 7); |
|
|
62 |
17 |
return ((tz & 1) == 1) || (((n>>tz) % 8) != 7); |
|
3663
|
20 |
5 |
while (b > c) { UV t = a % b; a = b; b = t; } |
|
3665
|
5 |
0 |
u = (u % d == 0) ? u/d : 0; |
|
3666
|
5 |
0 |
if (u && is_perfect_square_ret(u,&c)) { |
|
|
5 |
0 |
if (u && is_perfect_square_ret(u,&c)) { |
|
3680
|
0 |
0 |
if (roots) { |
|
3681
|
0 |
0 |
for (i = 0; i < nroots/2 && !success; i++) |
|
|
0 |
0 |
for (i = 0; i < nroots/2 && !success; i++) |
|
3692
|
1 |
17 |
if (p == 0) { |
|
3697
|
2 |
15 |
if (d == 0) { |
|
3698
|
1 |
1 |
if (!is_perfect_square_ret(p,&root)) return 0; |
|
3705
|
5 |
10 |
if (is_prime(p)) { |
|
3706
|
0 |
5 |
if (kronecker_uu(negd,p) == -1) return 0; |
|
3707
|
0 |
5 |
if (!sqrtmodp(&u, negd, p)) return 0; |
|
3711
|
0 |
10 |
if (((p >> 31) >> 22) && kronecker_uu(negd,p) != -1 && corn_all(x, y, d, p)) |
|
|
0 |
0 |
if (((p >> 31) >> 22) && kronecker_uu(negd,p) != -1 && corn_all(x, y, d, p)) |
|
|
0 |
0 |
if (((p >> 31) >> 22) && kronecker_uu(negd,p) != -1 && corn_all(x, y, d, p)) |
|
3718
|
166 |
0 |
for (u = 0, limu = isqrt(p/d); u <= limu; u++) { |
|
3720
|
10 |
156 |
if (is_perfect_square_ret(t,&root)) { |
|
3741
|
6 |
23486 |
if (x < 1) return 0; |
|
3742
|
10 |
23476 |
if (y <= 1) return 1; |
|
3743
|
4217 |
19259 |
if (y >= x) return x; |
|
3744
|
3 |
19256 |
if (y == 2) return 1 + log2floor(x); |
|
|
3 |
0 |
if (y == 2) return 1 + log2floor(x); |
|
3745
|
2 |
19254 |
if (!(y&1)) y--; /* Make y odd for simplicity */ |
|
3748
|
5537 |
13719 |
if (y == 7 && x- 7 <=128) return _psi_cache_v__7[x-1- 7]; |
|
|
4308 |
1229 |
if (y == 7 && x- 7 <=128) return _psi_cache_v__7[x-1- 7]; |
|
3749
|
3877 |
11071 |
if (y == 11 && x-11 <= 96) return _psi_cache_v_11[x-1-11]; |
|
|
3047 |
830 |
if (y == 11 && x-11 <= 96) return _psi_cache_v_11[x-1-11]; |
|
3750
|
2748 |
9153 |
if (y == 13 && x-13 <= 64) return _psi_cache_v_13[x-1-13]; |
|
|
1944 |
804 |
if (y == 13 && x-13 <= 64) return _psi_cache_v_13[x-1-13]; |
|
3751
|
7090 |
2867 |
if (y >= 17 && x <= 128) { |
|
|
4417 |
2673 |
if (y >= 17 && x <= 128) { |
|
3756
|
54637 |
15 |
for (i = 0, sum = x; i < 48 && x >= xt[i]; i++) |
|
|
50235 |
4402 |
for (i = 0, sum = x; i < 48 && x >= xt[i]; i++) |
|
3757
|
36256 |
13979 |
if (y < yt[i]) |
|
3765
|
5540 |
0 |
sum = 1 + log2floor(x); /* debruijn_psi(x,2) */ |
|
3768
|
5540 |
0 |
if (y >= 3) { |
|
3769
|
21355 |
5540 |
for (x3 = x/3; x3 > 3; x3 /= 3) |
|
3770
|
21355 |
0 |
sum += 1+log2floor(x3); |
|
3773
|
5537 |
3 |
if (y >= 5) { |
|
3774
|
12393 |
5537 |
for (x5 = x/5; x5 > 5; x5 /= 5) { |
|
3775
|
12393 |
0 |
sum += 1+log2floor(x5); |
|
3776
|
20577 |
12393 |
for (x3 = x5/3; x3 > 3; x3 /= 3) |
|
3777
|
20577 |
0 |
sum += 1+log2floor(x3); |
|
3782
|
5537 |
3 |
if (y >= 7) sum += debruijn_psi(x/ 7, 7); |
|
3783
|
4307 |
1233 |
if (y >= 11) sum += debruijn_psi(x/11,11); |
|
3784
|
3477 |
2063 |
if (y >= 13) sum += debruijn_psi(x/13,13); |
|
3785
|
2673 |
2867 |
if (y >= 17) sum += debruijn_psi(x/17,17); |
|
3786
|
2337 |
3203 |
if (y >= 19) sum += debruijn_psi(x/19,19); |
|
3787
|
2085 |
3455 |
if (y >= 23) sum += debruijn_psi(x/23,23); |
|
3788
|
1909 |
3631 |
if (y >= 29) { |
|
3789
|
1909 |
0 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
|
0 |
1909 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
|
0 |
31379 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
|
5427 |
25952 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
|
374 |
5053 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
|
0 |
5053 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
|
374 |
5053 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
|
0 |
31005 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
|
1535 |
29470 |
START_DO_FOR_EACH_PRIME(29, y) { |
|
3791
|
3037 |
26433 |
sum += (p >= xp) ? xp : debruijn_psi(xp, p); |
|
3799
|
18 |
19 |
if (y <= 2) return x; |
|
3800
|
6 |
13 |
if (y <= 3) return x - x/2; |
|
3801
|
12 |
1 |
if (y <= 5) return x - x/2 - x/3 + x/6; |
|
3809
|
0 |
1 |
if (n < 1) |