src/nt/prime_seq/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../math/iroot/sqrt/lib.hpp" | ||
| 4 | #include "../../util/alias/others/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | 646 | CEXP vecu prime_seq(u32 n) NE { | |
| 9 | 646 | vecb sieve(n / 3 + 1, true); | |
| 10 |
2/2✓ Branch 1 taken 96354 times.
✓ Branch 2 taken 646 times.
|
97000 | for (u32 p = 5, d = 4, i = 1, sqn = isqrt(n); p <= sqn; p += d = 6 - d, ++i) { |
| 11 |
2/2✓ Branch 2 taken 50825 times.
✓ Branch 3 taken 45529 times.
|
96354 | if (!sieve[i]) continue; |
| 12 |
2/2✓ Branch 3 taken 1233180838 times.
✓ Branch 4 taken 45529 times.
|
1233226367 | for (u64 q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p, qe = sieve.size(); q < qe; q += r = s - r) sieve[q] = false; |
| 13 | } | ||
| 14 | 1292 | vecu ret{2, 3}; | |
| 15 |
2/2✓ Branch 0 taken 747311716 times.
✓ Branch 1 taken 646 times.
|
747312362 | for (u32 p = 5, d = 4, i = 1; p <= n; p += d = 6 - d, ++i) |
| 16 |
2/2✓ Branch 2 taken 122665458 times.
✓ Branch 3 taken 624646258 times.
|
747311716 | if (sieve[i]) ret.push_back(p); |
| 17 |
6/6✓ Branch 2 taken 714 times.
✓ Branch 3 taken 31 times.
✓ Branch 5 taken 99 times.
✓ Branch 6 taken 615 times.
✓ Branch 7 taken 99 times.
✓ Branch 8 taken 646 times.
|
745 | while (!ret.empty() && ret.back() > n) ret.pop_back(); |
| 18 | 646 | return ret; | |
| 19 | 646 | } | |
| 20 | |||
| 21 | } // namespace tifa_libs | ||
| 22 |