| line |
true |
false |
branch |
|
28
|
7 |
23250 |
if (n < 2) return 0; |
|
30
|
6326 |
16924 |
if (!(n&1)) { |
|
31
|
6306 |
20 |
if (n & (n-1)) return 0; |
|
32
|
16 |
4 |
if (prime) *prime = 2; |
|
33
|
20 |
0 |
return ctz(n); |
|
35
|
2137 |
14787 |
if ((n%3) == 0) { |
|
37
|
3324 |
30 |
do { n /= 3; power++; } while (n > 1 && (n%3) == 0); |
|
|
1217 |
2107 |
do { n /= 3; power++; } while (n > 1 && (n%3) == 0); |
|
38
|
2107 |
30 |
if (n != 1) return 0; |
|
39
|
17 |
13 |
if (prime) *prime = 3; |
|
42
|
2859 |
11928 |
if ((n%5) == 0) { |
|
43
|
3618 |
22 |
do { n /= 5; power++; } while (n > 1 && (n%5) == 0); |
|
|
781 |
2837 |
do { n /= 5; power++; } while (n > 1 && (n%5) == 0); |
|
44
|
2837 |
22 |
if (n != 1) return 0; |
|
45
|
15 |
7 |
if (prime) *prime = 5; |
|
48
|
1638 |
10290 |
if ((n%7) == 0) { |
|
49
|
1957 |
18 |
do { n /= 7; power++; } while (n > 1 && (n%7) == 0); |
|
|
337 |
1620 |
do { n /= 7; power++; } while (n > 1 && (n%7) == 0); |
|
50
|
1620 |
18 |
if (n != 1) return 0; |
|
51
|
12 |
6 |
if (prime) *prime = 7; |
|
54
|
3683 |
6607 |
if (is_prob_prime(n)) |
|
55
|
2761 |
922 |
{ if (prime) *prime = n; return 1; } |
|
58
|
132 |
6475 |
if (power) { |
|
59
|
114 |
18 |
if (is_prob_prime(root)) |
|
60
|
110 |
4 |
{ if (prime) *prime = root; } |
|
72
|
3 |
51 |
if (n < 2) return 2; |
|
73
|
0 |
51 |
if (n >= MPU_MAX_PRIME) return 0; /* Overflow (max power = max prime) */ |
|
82
|
51 |
0 |
bit = UVCONST(1) << log2floor(n); |
|
83
|
46 |
13 |
for (i = n+1+(n&1); i & bit; i += 2) |
|
84
|
38 |
8 |
if (is_prime_power(i)) |
|
93
|
4 |
52 |
if (n <= 2) return 0; |
|
101
|
52 |
0 |
bit = UVCONST(1) << log2floor(n); |
|
102
|
42 |
15 |
for (i = n-!(n&1); i & bit; i -= 2) |
|
103
|
37 |
5 |
if (is_prime_power(i)) |
|
113
|
47 |
0 |
if (hi < 2 || lo > hi) { *list = 0; return 0; } |
|
|
0 |
47 |
if (hi < 2 || lo > hi) { *list = 0; return 0; } |
|
116
|
47 |
0 |
log2n = log2floor(hi); |
|
117
|
173 |
47 |
for (k = 2; k <= log2n; k++) { |
|
119
|
168 |
5 |
if (lo > 2) npmax -= prime_count_lower(rootint(lo-1,k)); |
|
122
|
0 |
47 |
New(0, powers, npmax, UV); |
|
125
|
173 |
47 |
for (k = 2; k <= log2n; k++) { |
|
126
|
173 |
0 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
|
173 |
0 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
|
431 |
284 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
|
258 |
173 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
|
173 |
85 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
|
46 |
238 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
|
1 |
45 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
|
0 |
45 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
|
1 |
45 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
|
0 |
283 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
|
172 |
542 |
START_DO_FOR_EACH_PRIME(2, rootint(hi,k)) { |
|
128
|
227 |
315 |
if (pk >= lo) powers[np++] = pk; |
|
142
|
47 |
0 |
if (hi < 2 || lo > hi) { *list = 0; return 0; } |
|
|
0 |
47 |
if (hi < 2 || lo > hi) { *list = 0; return 0; } |
|
153
|
1 |
46 |
if (npower == 0) { Safefree(powers); *list = primes; return nprime; } |
|
158
|
0 |
46 |
New(0, tot, ntotal, UV); |
|
159
|
779 |
46 |
for (i = 0; i < ntotal; i++) { |
|
160
|
70 |
709 |
if (ipower == npower) tot[i] = primes[iprime++]; |
|
161
|
20 |
689 |
else if (iprime == nprime) tot[i] = powers[ipower++]; |
|
162
|
482 |
207 |
else tot[i] = (primes[iprime] < powers[ipower]) ? primes[iprime++] : powers[ipower++]; |
|
172
|
198 |
8 |
if (hi < 2 || hi < lo) return 0; |
|
|
0 |
198 |
if (hi < 2 || hi < lo) return 0; |
|
173
|
92 |
106 |
return prime_power_count(hi) - ((lo <= 2) ? 0 : prime_power_count(lo-1)); |
|
181
|
50 |
435 |
if (n <= 5) return (n==0) ? 0 : n-1; |
|
|
50 |
0 |
if (n <= 5) return (n==0) ? 0 : n-1; |
|
184
|
435 |
0 |
log2n = log2floor(n); |
|
185
|
1970 |
435 |
for (k = 2; k <= log2n; k++) |
|
194
|
6 |
320 |
if (n <= 5) return (n==0) ? 0 : n-1; |
|
|
5 |
1 |
if (n <= 5) return (n==0) ? 0 : n-1; |
|
197
|
320 |
0 |
log2n = log2floor(n); |
|
198
|
4330 |
320 |
for (k = 2; k <= log2n; k++) |
|
206
|
6 |
327 |
if (n <= 5) return (n==0) ? 0 : n-1; |
|
|
5 |
1 |
if (n <= 5) return (n==0) ? 0 : n-1; |
|
209
|
327 |
0 |
log2n = log2floor(n); |
|
210
|
4504 |
327 |
for (k = 2; k <= log2n; k++) |
|
218
|
6 |
786 |
if (n <= 5) return (n==0) ? 0 : n-1; |
|
|
5 |
1 |
if (n <= 5) return (n==0) ? 0 : n-1; |
|
221
|
786 |
0 |
log2n = log2floor(n); |
|
222
|
8752 |
786 |
for (k = 2; k <= log2n; k++) |
|
228
|
93 |
74 |
if (n <= 100) return n+1; |
|
237
|
5 |
35 |
if (n <= 7) return (n==0) ? 0 : n+1+(n/5); |
|
|
5 |
0 |
if (n <= 7) return (n==0) ? 0 : n+1+(n/5); |
|
244
|
5 |
35 |
if (n <= 7) return (n==0) ? 0 : n+1+(n/5); |
|
|
5 |
0 |
if (n <= 7) return (n==0) ? 0 : n+1+(n/5); |
|
251
|
5 |
97 |
if (n <= 7) return (n==0) ? 0 : n+1+(n/5); |
|
|
5 |
0 |
if (n <= 7) return (n==0) ? 0 : n+1+(n/5); |
|
257
|
7 |
62 |
if (n <= 7) return (n==0) ? 0 : n+1+(n/5); |
|
|
7 |
0 |
if (n <= 7) return (n==0) ? 0 : n+1+(n/5); |
|
258
|
0 |
62 |
if (n >= MPU_MAX_PRIME_IDX) return MPU_MAX_PRIME; |